#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#define pb push_back
using namespace std;
int cost=0,n,m,t[100010],r[100010];
struct muchie{
    int x,y,c;
}v[100010];
vector <pair<int,int> > a;
bool mm(muchie a,muchie b){
    return a.c<b.c;
}
void citire(){
    ifstream f("apm.in");
    int x,y,c,i; f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y>>c;
        v[i].x=x;
        v[i].y=y;
        v[i].c=c;
    }
    sort(v+1,v+m+1,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 t1,int t2){
    if(r[t1]<r[t2]) t[t1]=t2;
    else if(r[t2]>r[t1]) t[t2]=t1;
    else{
        t[t1]=t2; r[t2]++;
    }
}
void rezolvare(){
    int i,t1,t2;
    for(i=0;i<m;i++){
        t1=tata(v[i].x);
        t2=tata(v[i].y);
        if(t1!=t2){
            unire(t1,t2);
            a.pb(make_pair(v[i].x,v[i].y));
            cost+=v[i].c;
        }
    }
}
void afisare(){
    ofstream o("apm.out");
    o<<cost<<"\n"<<a.size()<<"\n";
    int i;
    for(i=0;i<a.size();i++)
        o<<a[i].first<<" "<<a[i].second<<"\n";
    o.close();
}
int main(){
    citire();
    rezolvare();
    afisare();
}