#include <cstdio>
#include <algorithm>

using namespace std;
pair <int,pair <int,int> > v[400001];
pair <int,int> arb[200001];
int t[200001];
int rad (int x){
    while (t[x]>0)
        x=t[x];
    return x;
}
int main()
{
    FILE *fin=fopen ("apm.in","r");
    FILE *fout=fopen ("apm.out","w");
    int n,m,i,sol,mu,x,y,rx,ry;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=n;i++)
        t[i]=-1;
    for (i=1;i<=m;i++)
        fscanf (fin,"%d%d%d",&v[i].second.first,&v[i].second.second,&v[i].first);
    sort (v+1,v+m+1);
    sol=0;
    mu=0;
    for (i=1;i<=m;i++){
        x=v[i].second.first;
        y=v[i].second.second;
        rx=rad(x);
        ry=rad(y);
        if (rx!=ry){
            // trb sa le unesc pe x si y
            sol+=v[i].first;
            mu++;
            arb[mu].first=x;
            arb[mu].second=y;
            if (t[rx]<t[ry]){
                t[rx]+=t[ry];
                t[ry]=rx;
            }
            else {
                t[ry]+=t[rx];
                t[rx]=ry;
            }
        }
    }
    fprintf (fout,"%d\n%d\n",sol,mu);
    for (i=1;i<=mu;i++)
        fprintf (fout,"%d %d\n",arb[i].first,arb[i].second);
    return 0;
}