#include<algorithm>
#include<fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct rez{
    int x,y;
}v1[400010];
struct muchie{
int x,y,c;
};
muchie v[400010];
int n, m, suma, a[200010], t3;

int test(muchie t1, muchie t2)
{ return t1.c<=t2.c;}

void citire(){
    f>>n>>m;
    for( int i=1;i<=m;++i)
        f>>v[i].x>>v[i].y>>v[i].c;
}

void apm(){
    for(int i=1;i<=n;++i) a[i]=i;
    int k=0;int p=1;
    while (k<n-1)
    {
    if(a[v[p].x]!=a[v[p].y])
    {
        //g<<v[p].x<<' '<<v[p].y<<' '<<v[p].c<<'\n';
        v1[t3].x=v[p].x;
        v1[t3++].y=v[p].y;
        suma+=v[p].c;
        k++;
        int w=a[v[p].x], w1=a[v[p].y];
        for(int i=1;i<=n;++i)
            if(a[i]==w)
                a[i]=w1;
    }
    p++;
    }
}

int main(){
    citire ();
    sort(v+1,v+m+1,test);
    apm();
    g<<suma<<'\n'<<n-1<<'\n';
    for(int i=0;i<n-1;++i)
        g<<v1[i].x<<' '<<v1[i].y<< '\n';
    g.close();
    return 0;
}