#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int N,M,i,rx,ry,c,k;
int t[100010];
pair <int , pair<int,int> > f[400010];
pair <int,int> sol[200010];
int rad(int x){
    while(t[x]>0){
        x=t[x];
    }
    return x;
}
int main(){
    fin>>N>>M;
    for(i=1;i<=N;i++)
        t[i]=-1;
    for(i=1;i<=M;i++){
        fin>>f[i].second.first>>f[i].second.second>>f[i].first;
    }
    sort(f+1,f+M+1);
    for(i=1;i<=M;i++){
            rx=rad(f[i].second.first);
            ry=rad(f[i].second.second);
            if(rx!=ry){
                sol[++k].first=f[i].second.first;
                sol[k].second=f[i].second.second;
                c+=f[i].first;
                if(t[rx]<t[ry]){
                    t[rx]+=t[ry];
                    t[ry]=f[i].second.first;
                }
                else{
                    t[ry]+=t[rx];
                    t[rx]=ry;
                }
            }
    }


    fout<<c<<"\n"<<k<<"\n";
    for(i=1;i<=k;i++)
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";

    return 0;
    }