#include <iostream>
#include <algorithm>
#include <fstream>

using namespace std;

#define maxn 200000

ifstream f("apm.in");
ofstream g("apm.out");

int n, m;
int ind[maxn], n1[maxn], n2[maxn], cost[maxn], GR[maxn];
int compConex[maxn];
int costFinal;
int graf[maxn][2];

bool cmpf( int i, int j) {
    return true;
}

void read() {
    f >> n >> m;
    int i;
    for( i = 1; i <= m; i++) {
        f >> n1[i] >> n2[i] >> cost[i];
        ind[i] = i;
    }
}

int grupa(int i)
{
	if (GR[i] == i) return i;
	GR[i] = grupa(GR[i]);
	return GR[i];
}

void reuniune(int i,int j)
{
	GR[grupa(i)] = grupa(j); 
}

bool comp(int i, int j)
{
	return ( cost[i] < cost[j] );
}



void kruskal() {
    sort( ind + 1, ind + 1 + m, comp);
    for( int i = 1; i <= n; i++) GR[i] = i;
    int no = 0;
    for(int i = 1; i <= m; i++) {
        if( grupa( n1[ ind[i] ] ) != grupa( n2[ ind[i] ] ) ) {
            costFinal = costFinal + cost[ ind[i] ]; cout << cost[ind[i]] << " ";
            graf[no][0] = n1[ ind[i] ] ;
            graf[no][1] = n2[ ind[i] ] ;
            no++;
            reuniune( n1[ ind[i] ], n2[ ind[i] ] );
        }
    }

}

void afis() {
    g << costFinal;
    g << "\n" << n-1 << "\n";
    for( int i = 0; i < n; i++) 
        g << graf[i][0] << " " << graf[i][1] << "\n";
}

int main() {
    read();
    kruskal();
    afis();
    return 0;
}