//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,s,Viz[200005],nr,Sol1[200005],Sol2[200005];
struct muchie
{
    int i; bool viz;
    int j;
    int c;
}X[400005];
void citire()
{
    in>>n>>m;
    for(int p=1;p<=m;p++)
        in>>X[p].i>>X[p].j>>X[p].c;
}
bool comp (muchie e1 , muchie e2) {return e1.c <e2.c; }
void Kruskal()
{ int k,l,o;
    sort(X+1,X+m+1,comp);
    for(k=1;k<=n;k++)
        Viz[k]=k;
    k=0;
    for(l=1;l<=n-1;l++)
    { k++;
        while(k<=m&&Viz[X[k].i]==Viz[X[k].j])
            k++;
        if(k<=m)
        { int temp=Viz[X[k].j];
           for(o=1;o<=n;o++)
             if(Viz[o]==temp)
             Viz[o]=Viz[X[k].i];
        }
    nr++; Sol1[nr]=X[k].i; Sol2[nr]=X[k].j; X[k].viz=1; s=s+X[k].c;
    }
}
int main()
{
    citire();
    Kruskal();
    out<<s<<"\n";
    out<<nr<<"\n";
    for(int i=1;i<=nr;i++)
    {
       out<<Sol1[i]<<" "<<Sol2[i];
       out<<"\n";
    }
    return 0;
}