#include <iostream>
#include<fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,s[10000],t[10000],ct=0,nr=0;
int a[2000][4000];
void citire(){
    int x,y,c;
    f>>n>>m;
    for(int i=1;i<=m;i++){
        f>>x>>y>>c;
        a[x][y]=c;
        a[y][x]=c;
        }
}
void prim(){
    int v,v1,v2;
    s[1]=1;
    for(int k=1;k<n;k++){
        int minn=1001;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(a[i][j]<minn && s[i]==1 && s[j]==0 && a[i][j]!=0)
                    {
                        minn=a[i][j];
                        v1=i;
                        v2=j;
                    }
        s[v2]=1;
        t[v2]=v1;
    }
}
int main()
{
    citire();
    prim();
    for(int i=1;i<=n;i++)
        if(t[i]!=0){
        ct+=a[t[i]][i];
            nr++;
        }
    g<<ct<<endl<<nr<<endl;
    for(int i=1;i<=n;i++)
        if(t[i]!=0)
            g<<t[i]<<" "<<i<<endl;
    return 0;
}