#include<fstream>
#define INF 999999
using namespace std;

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

int n,m,a[100][100];

void citire()
{
    fin>>n>>m;
    int x,y,z,i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            a[i][j]=INF;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        a[x][y]=a[y][x]=z;
    }
}
int viz[100];

void prim()
{
    viz[1]=1;int sum=0;
    int p,mini=INF,i,j,mx,my;
    for(p=1;p<=n-1;p++)
    {
        mini=INF;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(viz[i]==1 and viz[j]==0)
                    if(mini>a[i][j])
                        {mini=a[i][j];mx=i;my=j;}
        fout<<mx<<" "<<my<<'\n';
        sum+=mini;
        viz[my]=1;
    }
    fout<<sum;
}

int main()
{
    citire();
    prim();
    return 0;
}