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

using namespace std;

struct muchii
{
    int a,b,c;
} 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 verif(int x,int y)
{
    while(tata[x]!=0 && x!=y)
        x=tata[x];
    while(tata[y]!=0 && x!=y)
        y=tata[y];
    if(x==y)
        return 0;
    else
        return 1;
}

int main()
{
    int n,i,t,x,nr=0,s=0,m,y,aux,k;
    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<=m;i++)
    {
        if(verif(v[i].a,v[i].b)==1)
        {
            s+=v[i].c;
            nr++;
            x=v[i].a;
            t=tata[x];
            while(t!=0)
            {
                y=x;
                x=t;
                t=tata[x];
                tata[x]=y;
            }
            tata[v[i].a]=v[i].b;
            if(nr==n-1)
            {
                break;
            }
        }
    }
    out<<s<<endl<<n-1<<endl;
    for(i=1;i<=n;i++)
    {
        if(tata[i]!=0)
        {
            out<<i<<" "<<tata[i]<<endl;
        }
    }
    return 0;
}