#include <fstream>
#include <algorithm>
using namespace std;
FILE*fin;
ofstream fout("apm.out");
struct muchie
{
  int x,y,c;
}v[400001];
struct afis
{
    int y,z;
}x[400001];
int cond(muchie a,muchie b)
{
    if(a.c>b.c)
        return 0;
    return 1;
}
int n,m,i,l[200001],k,a,b,ct,aa,bb,j;
int main()
{
    fin=fopen("apm.in","r");
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
        fscanf(fin,"%d%d%d",&v[i].x,&v[i].y,&v[i].c);
    for(i=1;i<=n;i++)
        l[i]=i;
    i=1;
    sort(v+1,v+m+1,cond);
    while(k<n-1)
    {
        a=v[i].x;
        b=v[i].y;
        if(l[a]!=l[b])
        {
            k++;
            x[k].y=a;
            x[k].z=b;
            aa=l[a];
            bb=l[b];
            for(j=1;j<=n;j++)
                if(l[j]==aa)
                    l[j]=bb;
            ct+=v[i].c;
        }
        i++;
    }
    fout<<ct<<'\n'<<k<<'\n';
    for(i=1;i<=k;i++)
        fout<<x[i].y<<' '<<x[i].z<<'\n';
    return 0;
}