#include <iostream>
#include <fstream>
#define INF 999999
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int a[1001][1001],t[1001],use[1001],b[1001],cmin[1001],h,ct,n,m;
void prim(int x)
{
    int i,j,k,mn,p;
    for(i=1;i<=n;i++)
    {
        cmin[i]=a[x][i];
        t[i]=x;
    }
    use[x]=1;
    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;
            }
        }
        use[p]=1;
        b[++h]=p;
        ct+=mn;
        for(i=1;i<=n;i++)
        {
            if(a[p][i]<cmin[i]&&!use[i])
            {
                cmin[i]=a[i][p];
                t[i]=p;
            }
        }

    }

    g<<ct<<'\n'<<h<<'\n';
    for(i=1;i<=h;i++)
        g<<b[i]<<" "<<t[b[i]]<<'\n';
}

int main()
{
    int i,j,x,y,c;

    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        a[i][j]=INF;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        a[x][y]=c;
        a[y][x]=c;
    }
    prim(1);
    return 0;
}