#include <fstream>
#include <algorithm>
using namespace std;
struct punct
{
    int x,y,c,sel;
}v[10001];
int compare (punct a, punct b)
{
    return (a.c<b.c);
}
int n,m,i,j,nr,ct,t,q,c[10001];
int main()
{
    ifstream fin ("apm.in");
    ofstream fout ("apm.out");
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v+1,v+m+1,compare);
    for (i=1;i<=n;i++)
        c[i]=i;
    nr=0;
    i=1;
    while (nr<n-1)
    {
        if (c[v[i].x]!=c[v[i].y])
        {
            nr++;
            ct=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++;
    }
    fout<<ct<<'\n'<<n-1<<'\n';
    nr=0;
    i=1;
    while (nr<n-1)
    {
        if (v[i].sel==1) {fout<<v[i].y<<" "<<v[i].x<<'\n';nr++;}
        i++;
    }
    return 0;
}