#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,i,nr,c[1001],t,q,j,ct;
struct muchii
{int x,y,c,sel;

}v[10001];
int compare(muchii a,muchii b)
{return (a.c<b.c);

}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
        c[i]=i;


    for(i=1;i<=m;i++)
    {f>>v[i].x>>v[i].y>>v[i].c;
        v[i].sel=0;
    }
    sort(v+1,v+m+1,compare);


     nr=0;ct=0;
    i=1;
    while(nr<n-1)
    {if(c[v[i].x]!=c[v[i].y])
    {nr++;
    ct+=v[i].c;
    v[i].sel=1;
    t=min(c[v[i].x],c[v[i].y]);
    q=max(c[v[i].x],c[v[i].y]);
    for(j=1;j<=n;j++)
    {if(c[j]==q)c[j]=t;

    }
    }
     i++;
    }
    g<<ct<<'\n';
    g<<n-1<<'\n';
    nr=0;i=1;
    while(nr<n-1){
        if(v[i].sel==1){
            nr++;
            g<<v[i].y<<" "<<v[i].x<<'\n';

        }
    i++;
    }
    return 0;
}