#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#define pb push_back
using namespace std;
int cost=0,k=0,n,m,t[200010],r[200010];
struct nod{int x,y,c;};
vector <nod> v;
pair<int,int> p[400010];
bool mm(nod a,nod b){
    return a.c<b.c;
}
void citire(){
    ifstream f("apm.in");
    int x,y,c,i; f>>n>>m;
    nod p;
    for(i=1;i<=m;i++){
        f>>p.x>>p.y>>p.c;
        v.pb(p);
    }
    sort(v.begin(),v.end(),mm);
    for(i=1;i<=n;i++)
        t[i]=i,r[i]=1;
    f.close();
}
int tata(int nod){
    while(t[nod]!=nod)
        nod=t[nod];
    return nod;
}
void unire(int noda,int nodb){
    if(r[noda]<r[nodb]) t[noda]=nodb;
    else if(r[nodb]>r[noda]) t[nodb]=noda;
    else{
        t[noda]=nodb; r[nodb]++;
    }
}
void solve(){
    int t1,t2;
    for(int i=0;i<m;i++){
        t1=tata(v[i].x);
        t2=tata(v[i].y);
        if(t1!=t2){
            unire(t1,t2);
            p[++k].first=v[i].x;
            p[k].second=v[i].y;
            cost+=v[i].c;
        }
    }
}

void afis(){
    ofstream o("apm.out");
    o<<cost<<"\n";
    o<<n-1<<"\n";
    for(int i=1;i<n;i++)
        o<<p[i].first<<" "<<p[i].second<<"\n";
    o.close();
}
int main(){
    citire();
    solve();
    afis();
}