#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],rang[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 x, int y)
{
    if(rang[x]>rang[y])
        t[y]=x;
    if(rang[y]>rang[x])
        t[x]=y;
    if(rang[x]==rang[y])
    {
        t[y]=x;
        rang[x]++;
    }
}

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;
            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;
}