#include <bits/stdc++.h>
using namespace std;
fstream in("apm.in");
ofstream out("apm.out");
struct arb{
    int x,y,c;
};
arb a[1000],b[1000];
int n,m,t[1000];
bool cmp(arb e1,arb e2){
    return e1.c<e2.c;
}
int nr=0;
void afis(int n,int m){
    out<<endl<<nr<<endl;
    for(int i=1;i<=nr;i++)out<<b[i].x<<" "<<b[i].y<<endl;
}
int kruskal(int n,int m){
    for(int i=1;i<=n;i++)t[i]=i;
    int s=0;
    for(int i=1;i<=m;i++){
        if(t[a[i].x]!=t[a[i].y]){
            s+=a[i].c;
            b[++nr]=a[i];
            int ai=t[a[i].x],aj=t[a[i].y];
            for(int j=1;j<=n;j++){
                if(t[j]==aj)t[j]=ai;
            }
        }
    }
    return s;
}
int main(){
    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>a[i].x>>a[i].y>>a[i].c;
    }
    sort(a+1,a+m+1,cmp);
    out<<kruskal(n,m);
    afis(n,m);

}