#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int N=4e5;
int n,m,tmp[N];
int tata[N/2],h[N/2];
void init(int u){
    tata[u] = 0;
    h[u] = 0;
}
int reprez(int u){
    while(tata[u] != 0) u = tata[u];
    return u;
}
int reuneste(int u, int v){
    int ru, rv;
    ru = reprez(u);
    rv = reprez(v);
    if(h[ru] > h[rv]){
        tata[rv] = ru;
    }
    else{
        tata[ru] = rv;
    }
    if(h[ru] == h[rv]){
        h[rv]++;
    }
}
struct arc{
    int x,y,c;
}a[N];
void merge_sort(arc a[N],int st,int dr){
	if(st<dr){
		int m=(st+dr)/2;
		merge_sort(a,st,m);
		merge_sort(a,m+1,dr);
		int i=st,j=m+1,k=0;
		while(i<=m&&j<=dr)
			if(a[i].c<a[j].c)
				tmp[++k]=a[i++].c;
			else
				tmp[++k]=a[j++].c;
		while(i<=m)
			tmp[++k]=a[i++].c;
		while(j<=dr)
			tmp[++k]=a[j++].c;
		for(i=st,j=1;i<=dr;i++,j++)
			a[i].c=tmp[j];
	}
}
int main(){
    fin>>n>>m;
    for(int i=0;i<m;i++){
        fin>>a[i].x>>a[i].y>>a[i].c;
    }
    merge_sort(a,0,m-1);
    int cost = 0;
    int nr_m = 0;
    arc arb[n-1];
    for(int i=0;i<m;i++){
        if(reprez(a[i].x) != reprez(a[i].y)){
            cost += a[i].c;
            arb[nr_m++] = a[i];
            reuneste(a[i].x,a[i].y);
        }
    }
    fout<<cost<<"\n"<<nr_m<<"\n";
    for(int i=0;i<nr_m;i++){
        fout<<arb[i].x<<" "<<arb[i].y<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}