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

using namespace std;

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

const int MAX=4e5+5;
int n,m,cnt,t[MAX],rang[MAX],sol[MAX],cost;
struct M
{
    int a,b,c;
}mch[MAX];

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

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

void uneste(int x, int y)
{
    if(rang[x]<rang[y])
        t[x]=t[y];
    else
    {
        t[y]=t[x];
        if(rang[x]==rang[y])
            rang[x]++;
    }
}

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