#include<iostream>
#include<fstream>
#include<stdlib.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,c[200001],ct;
struct muchie{
    int x,y,c;
}v[400001],h[400001];
typedef muchie*pm;
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]);
}*/
int fcmp(const void *a,const void *b){
    return ((pm)a)->c-((pm)b)->c;
}
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();
    qsort(v+1,m,sizeof(v[0]),fcmp);
    //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;
}