#include <bits/stdc++.h>

using namespace std;

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

//vector<int> t[200001];
struct ab
{
    int x;
    int y;
    int c;
};
int p[200001],r[200001],i,j,m,n,a,b,x,y,rs,v;
ab t[400001],s[200001];


bool comp(ab a, ab b)
{
    return b.c>a.c;
}

int parinte(int nod)
{
    while (p[nod]!=nod)
        nod=p[nod];
    return nod;
}

int main()
{
    fin>>n>>v;
    for (i=1;i<=v;i++)
    {
        fin>>t[i].x>>t[i].y>>t[i].c;
        p[i]=i;
    }
    sort(t+1,t+v+1,comp);
    for (i=1;i<=v;i++)
    {
        x=parinte(t[i].x);
        y=parinte(t[i].y);
        if (x!=y)
        {
            rs+=t[i].c;
            m++;
            s[m].x=t[i].x;
            s[m].y=t[i].y;
            if (r[x]>r[y])
                 p[y]=x;
            else
            if (r[x]<r[y])
                 p[x]=y;
            else
            {
                r[x]++;
                p[y]=x;
            }
        }
    }
    fout<<rs<<"\n"<<m<<"\n";
    for (i=1;i<=m;i++)
        fout<<s[i].x<<" "<<s[i].y<<"\n";
    return 0;
}