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

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int MAX=200005;

struct T
{
    int a,b,c;
}v[2*MAX],af[MAX];

bool cmp(T x, T y)
{
    return x.c<y.c;
}

int n,m,a,b,c,k,cnt,cost,arb[MAX],A,B;

int main()
{
    fin >> n >> m;
    for(int i=1;i<=m;i++)
        fin >> v[i].a >> v[i].b >> v[i].c;
    sort(v+1,v+m+1,cmp);
    for(int i=1;i<=n;i++)
        arb[i]=i;
    for(int i=1;i<=m && cnt<n-1;i++)
        if(arb[v[i].a]!=arb[v[i].b])
        {
            A=arb[v[i].a];
            B=arb[v[i].b];
            af[++cnt]=v[i];
            cost+=v[i].c;
            for(int j=1;j<=n;j++)
                if(arb[j]==B)
                    arb[j]=A;
        }
    fout << cost << '\n' << n-1 << '\n';
    for(int i=1;i<=cnt;i++)
        fout << af[i].a << " " << af[i].b << '\n';
	return 0;
}