#include<fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,v[100],i,j,s,nr;
struct muchie{ int x,y,c; };
muchie a[400000],b[400000];
void citire(){
f>>n>>m;
for(i=1;i<=m;++i)
    f>>a[i].x>>a[i].y>>a[i].c;
}
void sortare(){
    muchie aux;
    for(i=1;i<m;++i)
        for(j=i+1;j<=m;++j)
            if(a[i].c>a[j].c){
                aux=a[i];
                a[i]=a[j];
                a[j]=aux;
                }
}
void kruskal(){
    sortare();
    for(i=1;i<=n;++i) v[i]=i;
    int k=1,t,w;
    while(nr<n-1){
        if(v[a[k].x]!=v[a[k].y]){
            b[k]=a[k];
            nr++;
            s=s+a[k].c;
            t=v[a[k].x];
            w=v[a[k].y];
            for(i=1;i<=n;++i)
                if(v[i]==w)
                    v[i]=t;
        }
        k++;
    }
}
int main(){
    citire();
    kruskal();
    g<<s<<'\n'<<nr<<'\n';
    for(j=1;j<=nr;++j)
        g<<b[j].y<<' '<<b[j].x<<'\n';
    g.close();
    return 0;
    }