#include <iostream>	
#include <fstream>
#include <algorithm>
	
using namespace std;
	
const int N = 2e5 + 5;	
	
int tati[N];	
int raspuns[2*N];
	
struct muchie{	
    int x,y,cost;
}muchii[N];
	
bool criteriu(muchie a, muchie b){
	
    return a.cost<b.cost;
	
}
	
int rad(int x){
    if(tati[x] == x){
        return x;
    }
    else return tati[x] = rad(tati[x]);
}
	
int main() {
    int n,m,l=0;
    ifstream in("apm.in");
    ofstream out("apm.out");
    in>>n>>m;
    muchie w;
    for(int i=0;i<m;i++){
        in>>w.x>>w.y>>w.cost;
        muchii[i]=w;
    }
    for(int i=1;i<=n;i++){
        tati[i] = i;
    }
    long long cost = 0;
    sort(muchii,muchii+m,criteriu);
    for(int i=0;i<m;i++){
        int a,b;
        a = rad(muchii[i].x);
        b = rad(muchii[i].y);
        if(a!=b){
            cost += muchii[i].cost;
            tati[b] = tati[a];
            raspuns[l++] = muchii[i].x;
            raspuns[l++] = muchii[i].y;
        }
    }
    out<<cost<<'\n';
    out<<l/2<<'\n';
    for(int i=0;i<l;i+=2){
        out<<raspuns[i]<<' '<<raspuns[i+1]<<'\n';
    }
    return 0;
	
}