#include <bits/stdc++.h>
#define ff first
#define ss second
#define NMAX 200005
#define pb push_back
using namespace std;
const string file = "apm";

ifstream fin (file+".in");
ofstream fout (file+".out");
typedef long long ll;
typedef long double ld;
// E CU KRUSKAL
const ll INF = 9223372036854775807ll;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, inf = 2147483647;
int nods[NMAX], nodf[NMAX], cost[NMAX];  // nod start muchie, nod final muchie, cost muchie
vector <int> sol ;
int ind[NMAX]; // indicii dupa sortare in fct de cost muchie
int gr[NMAX]; // comp conexa din care face parte x
int N,M,S;
int grupa(int x)
{
    if(gr[x] == x) return x;
    gr[x]=grupa(gr[x]);
    return gr[x];
}
void reunion(int x, int y) // reuniune a doua comp conexe
{
    gr[grupa(x)] = grupa(y);
}
bool comp(int x, int y)
{
    return (cost[x] < cost[y]);
}
int main()
{
    fin >> N >> M;
    for(int i=1;i<=M;++i)
    {
        fin>>nods[i]>>nodf[i]>>cost[i];
        ind[i]=i;
    }
    for(int i=1;i<=N;++i) gr[i]=i;
    sort(ind+1,ind+M+1,comp);
    for(int i=1;i<=M;++i)
    {
        if(grupa(nods[ind[i]]) != grupa(nodf[ind[i]]))
            S += cost[ind[i]], reunion(nods[ind[i]], nodf[ind[i]]), sol.push_back(ind[i]);
    }
    fout<<S<<"\n";
    fout<<N-1<<"\n";
    for(int i=0;i<N-1;++i)
        fout<<nods[sol[i]] << " "<<nodf[sol[i]] << "\n";
    return 0;
}