#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

struct muchii
{
    int a,b,c,p;
} v[200050];
int tata[200050];

bool exec(muchii x,muchii y)
{
    if(x.c==y.c)
        return x.a<y.a;
    else
        return x.c<y.c;
}
int main()
{
    int x,m,n,j,i,s=0;
    ifstream in ("apm.in");
    ofstream out ("apm.out");
    in>>n>>m;
    for(i=1; i<=m; i++)
        in>>v[i].a>>v[i].b>>v[i].c;
    sort(v+1,v+m+1,exec);
    for(i=1; i<=n; i++)
        tata[i]=i;
    for(i=1; i<=m; i++)
    {
        if(tata[v[i].a]!=tata[v[i].b])
        {
            s+=v[i].c;
            v[i].p=1;
            x=tata[v[i].a];
            for(j=1; j<=n; j++)
                if(tata[j]==x)
                    tata[j]=tata[v[i].b];
        }
    }
    out<<s<<endl<<n-1<<endl;
    for(i=1; i<=m; i++)
        if(v[i].p==1)
            out<<v[i].b<<" "<<v[i].a<<endl;
    return 0;
}