#include <fstream>
#include <algorithm>
#define INF 20000
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int c[20000][20000],use[200005],t[200005],cmin[200005],sol[200005][10],n,m,ct;
void citire()
{
    int i,j,k,cost;
    f>>n>>m;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            c[i][j]=INF;
    for(k=1; k<=m; k++)
    {
        f>>i>>j>>cost;
        c[i][j]=c[j][i]=cost;
    }
}
void prim(int x)
{
    int i,j,k,mn,p;
    for(i=1; i<=n; i++)
    {
        cmin[i]=c[x][i];
        t[i]=x;
    }
    use[x]=1;
    sol[1][0]=0;
    sol[1][1]=x;
    for (k=2; k<=n; k++)
    {
        mn=INF;
        for(i=1; i<=n; i++)
            if (!use[i] && cmin[i]<mn)
            {
                mn=cmin[i];
                p=i;
            }
        if (mn==INF)
            break;
        use[p]=1;
        ct+=mn;
        sol[k][0]=t[p];
        sol[k][1]=p;
        for(i=1; i<=n; i++)
            if (!use[i] && c[p][i]<cmin[i])
            {
                cmin[i]=c[p][i];
                t[i]=p;
            }
    }
}
int main()
{
    int i,j;
    citire();
    prim(1);
    g<<ct<<'\n'<<n-1<<'\n';
    for (i=2; i<=n; i++)
            g<<sol[i][1]<<" "<<sol[i][0]<<'\n';
    return 0;
}