#include<fstream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
const int Nmax = 200001;
 
int N, M, T[Nmax], L(-1), cost;
vector<pair<int, pair<int, int> > > G;
vector<pair<int, int> > sol;
 
ifstream f("apm.in");
ofstream g("apm.out");
 
int get_root(int x) {
    while(T[x]!=x)
        x=T[x];
    return x;
}
 
int main() {
    int k, i, j, c, root1, root2;
     
    f>>N>>M;
    G.resize(M); sol.resize(N-1);
    for(i=1; i<=N; i++)
        T[i]=i;
    for(k=0; k<M; k++) {
        f>>i>>j>>c;
        G[k].first=c; G[k].second.first=i; G[k].second.second=j;
    }
    sort(G.begin(),G.end());
    for(k=0; k<M; k++) {
        c=G[k].first;
        i=G[k].second.first;
        j=G[k].second.second;
        root1=get_root(i);
        root2=get_root(j);
        if(root1==root2)
            continue;
        if(root1>root2)
            T[root1]=T[root2];
        else
            T[root2]=T[root1];
        cost+=c; L++;
        sol[L].first=i; sol[L].second=j;
    }
    g<<cost<<" "<<"\n"<<N-1<<"\n";
    for(i=0; i<static_int<int>(sol.size()); i++)
        g<<sol[i].first<<" "<<sol[i].second<<"\n";
 
    f.close();
    g.close();
     
    return 0;
}