#include    <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");


struct graf{

    int x,y,c;
}g[100];

int t[100];
graf rez[100];
int n,m;
bool compara(graf a,graf b)
{
    if (a.c<b.c) return 1;
    return 0;
}

void citire()
{
    fin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        fin>>g[i].x>>g[i].y>>g[i].c;
    }
}

void rezolvare()
{
    int cnt=0;
    int cost=0;
    sort(g+1,g+1+n,compara);
    for (int i=1;i<=n;i++) t[i]=i;
    for (int i=1;i<=m;i++)
    {
        int k=g[i].x;
        int l=g[i].y;
        if (t[k]!=t[l])
        {
            rez[++cnt].x=k;
            rez[cnt].y=l;
            if (t[l]>t[k])
                t[l]=t[k];
            else t[k]=t[l];
            cost+=g[i].c;
        }
    }
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for (int i=1;i<n;i++)
        fout<<rez[i].y<<' '<<rez[i].x<<'\n';

}

int main()
{
    citire();
    rezolvare();
}