#include <bits/stdc++.h>
#define inf 100005

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m,c[805][805],cmin[805],use[805],t[805],q,ct,aa[1505],bb[1505];

void afis() {
    int i;
    g<<ct<<'\n'<<n-1<<'\n';
    for (i=1;i<n;i++)
        g<<aa[i]<<' '<<bb[i]<<'\n';
}

void prim(int x) {
    int i,j,k,mn,p;
    for (i=1;i<=n;i++)
        if (i!=x) {
            cmin[i]=c[x][i];
            t[i]=x;
        }
    use[x]=1;
    for (i=1;i<n;i++) {
        mn=inf;
        for (j=1;j<=n;j++)
            if (!use[j] && cmin[j]<mn) {
                mn=cmin[j];
                p=j;
            }
        if (mn==inf) break;
        ct+=mn;
        use[p]=1;
        aa[i]=t[p];
        bb[i]=p;
        //cout<<t[p]<<' '<<p<<'\n';
        for (j=1;j<=n;j++)
            if (cmin[j]>c[p][j] && !use[j]) {
                cmin[j]=c[p][j];
                t[j]=p;
            }
    }
    afis();
}

void init() {
    int i,j;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            c[i][j]=inf;
}

int main() {
    int i,j,x,y,z;
    f>>n>>m;
    init();
    for (i=1;i<=m;i++) {
        f>>x>>y>>z;
        c[x][y]=c[y][x]=z;
    }
    prim(1);
    return 0;
}