#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct muchie
{
    int i,j,cost;
}x[400005];
int n,m,t[200005],st[100003],dr[100003];
bool cmp(muchie i,muchie j)
{
    return(i.cost<j.cost);
}
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
        in>>x[i].i>>x[i].j>>x[i].cost;
    sort(x+1,x+m+1,cmp);
    for(int i=1;i<=n;i++)
        t[i]=i;
    int s=0,k=0;
    for(int i=0;i<m;i++)
        if(t[x[i].i]!=t[x[i].j])
    {
        s+=x[i].cost;
        dr[++k]=x[i].i;
        st[k]=x[i].j;
        int ai=t[x[i].i], aj=t[x[i].j];
        for(int j=1;j<=n;j++)
            if(t[j]==aj)
            t[j]=ai;
    }
    out<<s<<endl<<k<<endl;
    for(int i=1;i<=k;i++)
        out<<dr[i]<<' '<<st[i]<<endl;
    return 0;
}