#include <fstream>
#include <algorithm>
#define NMAX 100
#define MMAX 1000

using namespace std;

ifstream cin("amp.in");
ofstream cout("amp.out");

int n,m;
struct nod{int x,y,c;} v[MMAX],ss[NMAX];

int sol;

void read();
void solve();
bool compare(nod,nod);

int main()
{
    read();
    sort(v+1,v+m+1,compare);
    solve();
    cin.close();cout.close();
    return 0;
}

void read()
{
    int i;
    cin>>n>>m;
    for (i=1;i<=m;i++)
        cin>>v[i].x>>v[i].y>>v[i].c;
}

bool compare(nod a,nod b)
{
    return (a.c<b.c);
}

int c[NMAX];

void solve()
{
    int i,poz=1,nrx,nry,j;
    for (i=1;i<=n;i++) c[i]=i;
    for (i=1;i<n;i++)
    {
        while (c[v[poz].x]==c[v[poz].y]) poz++;
        ss[i]=v[poz];
        sol+=v[poz].c;
        nrx=c[v[poz].x];
        nry=c[v[poz].y];
        if (nrx>nry) swap(nrx,nry);
        for (j=1;j<=n;j++)
            if (c[j]==nry) c[j]=nrx;
    }
    cout<<sol<<'\n'<<n-1<<'\n';
    for (i=1;i<n;i++)
        cout<<ss[i].x<<' '<<ss[i].y<<'\n';
}