#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchii
{
    int x, y, d;
} v[400001];
struct muchii1
{
    int x,y;
} v1[400001];
int n, m, l[100], s,nr;
int comp(muchii a, muchii b)
{
    return a.d<b.d;
}
int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>v[i].x>>v[i].y>>v[i].d;
        l[i]=i;
    }
    sort(v+1, v+m+1, comp);
    for(int i=1; i<=m; i++)
    {
        if(l[v[i].x]!=l[v[i].y])
        {
            nr++;
            v1[nr].x=v[i].x;
            v1[nr].y=v[i].y;
            s=s+v[i].d;
            int a=l[v[i].y], b=l[v[i].x];
            for(int j=1; j<=m; j++)
            {
                if(a==l[j])
                {
                    l[j]=l[v[i].x];
                }
                if(b==l[j])
                {
                    l[j]=l[v[i].y];
                }
            }
        }
    }
    fout<<s<<'\n';
    fout<<nr<<'\n';
    for(int i=1;i<=nr;i++)
        fout<<v1[i].x<<' '<<v1[i].y<<'\n';
    fin.close();
    fout.close();
    return 0;
}