#include<iostream>
#include<fstream>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,c[100],ct;
struct muchie{
    int x,y,c;
}v[100],h[100];
void cit(){
    in>>n>>m;
    for(int i=1;i<=m;i++)
        in>>v[i].x>>v[i].y>>v[i].c;
}
void cost(){
    for(int i=1;i<m;i++)
        for(int j=i+1;j<=m;j++)
            if(v[i].c>v[j].c)
                swap(v[i],v[j]);
}
void init(){
    for(int i=1;i<=n;i++)
        c[i]=i;
}
void Kruskal(){
    int nrs=0,i=1;
    while(nrs!=n-1){
        while(c[v[i].x]==c[v[i].y])
                i++;
        nrs++;
        ct+=v[i].c;
        h[nrs]=v[i];
        int minim=c[v[i].x],maxim=c[v[i].y];
        if(minim>maxim)
            swap(minim,maxim);
        for(int j=1;j<=n;j++)
            if(c[j]==maxim)
                c[j]=minim;
        i++;
    }
}
int main(){
    cit();
    cost();
    init();
    Kruskal();
    out<<ct<<'\n'<<n-1<<'\n';
    for(int i=1;i<=n-1;i++)
        out<<h[i].x<<' '<<h[i].y<<'\n';
    return 0;
}