#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
int i,n,m,t[400010],C[400010],A[400010],j;

struct muchii{
    int x, y, c;


}
v[400010];

int cmp(muchii  a, muchii b){
    if(a.c<b.c)
        return 1;
return 0;
}
void update(int x, int y){

    while(t[x] > 0)
        x=t[x];
    while(t[y] > 0)
        y=t[y];
    if(t[x]<=t[y]){
        t[x]+=t[y];
        t[y]=x;
        if(C[x]==0)
            C[x]+=v[i].c;
        else
            if(C[y]==0)
                C[x]+=v[i].c;
            else
                C[x]+=C[y]+v[i].c;
    }
    else
        if(t[x]>t[y]){
            t[y]+=t[x];
            t[x]=y;
            C[y]+=C[x];
             if(C[y]==0)
                C[y]+=v[i].c;
                else
                    if(C[x]==0)
                        C[y]+=v[i].c;
                    else
                        C[y]+=C[x]+v[i].c;
        }
}
int query(int x, int y){
    int a = x;
    int b = y;
    while(t[x] > 0)
        x=t[x];
    while(t[y] > 0)
        y=t[y];
        if(x==y)
            return 0;
    A[++j]=a;
    A[++j]=b;
return 1;

}
int main()
{
    fin >> n >> m;
    for(i = 1;i <= m;i ++){
        fin >> v[i].x >> v[i].y>> v[i].c;
        //C[i]=v[i].c;
    }
    for(i = 1;i <= n;i ++)
        t[i] =- 1;
    sort(v + 1, v + m + 1,cmp);
    for(i = 1;i <= m;i ++)
        if(query(v[i].x,v[i].y))
            update(v[i].x,v[i].y);
    for(i=1;i<=n;i++)
        if(t[i]<0){
            fout<<C[i]<<'\n'<<-(t[i]+1)<<'\n';
            break;
        }
    for(i=1;i<=j;i++){
        fout<<A[i]<<" ";
        if(i%2 == 0)
        fout<<'\n';
    }
    return 0;
}