#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie{
    int nod1,nod2,cost;
}G[400005];

vector<muchie> solm;
int TT[200005],H[200005];
int n,m;

bool cmp(muchie a, muchie b){
    return a.cost < b.cost;
}

int root(int a){
    while(TT[a] != a){
        a = TT[a];
    }
    return a;
}

void unite(int a, int b){
    a = root(a);
    b = root(b);
    if(H[a] >= H[b]){
        TT[b] = a;
        H[a] = max(H[a],H[b]+1);
    }else{
        TT[a] = b;
        H[b] = max(H[b],H[a]+1);
    }
}

int main()
{
    int i,a,b,c,S=0,crt=0;
    fin>>n>>m;
    for(i = 1; i <= m; i++){
        fin>>a>>b>>c;
        G[i].nod1 = a;
        G[i].nod2 = b;
        G[i].cost = c;
    }
    sort(G+1,G+1+m,cmp);
    for(i = 1; i <= n; i++){
        TT[i] = i;
        H[i] = 1;
    }
    crt=0;
    for(i = 1; i <= m; i++){
        a = G[i].nod1;
        b = G[i].nod2;
        c = G[i].cost;
        if(root(a) != root(b)){
            unite(a,b);
            S+=c;
            muchie sol;

            sol.nod1 = a;
            sol.nod2 = b;
            sol.cost = c;
            solm.push_back(sol);

            crt++;
            if(crt == n-1){
                i = m+1;
            }
        }
    }
    fout<<S<<'\n';
    fout<<n-1<<'\n';
    for(i = 0; i < n-1; i++){
        fout<<solm[i].nod1<<' '<<solm[i].nod2<<'\n';
    }
    return 0;
}