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

using namespace std;

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

const int MAX=200005;
int n,m,a,b,c,cnt,cost,t[MAX],rx,ry;

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

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

int root(int x)
{
    while(t[x]!=x)
        x=t[x];
    return x;
}

void add(int rx,int ry)
{
    t[ry]=rx;
}

int main()
{
    fin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        fin >> v[i].a >> v[i].b >> v[i].c;
        t[i]=i;
    }
    sort(v+1,v+m+1,cmp);
    for(int i=1;cnt<n-1;i++)
    {
        rx=root(v[i].a);
        ry=root(v[i].b);
        if(rx!=ry)
        {
            af[++cnt]=v[i];
            cost+=v[i].c;
            t[ry]=rx;
            add(rx,ry);
        }
    }
    fout << cost << '\n' << n-1 << '\n';
    for(int i=1;i<=cnt;i++)
        fout << af[i].a << " " << af[i].b << '\n';
	return 0;
}