#include <cstdio>
#include <set>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

#define NMAX 200010
#define INF 0x3f3f3f3f

int N, M;
int use[NMAX];
int parent[NMAX];
int cost[NMAX];
int in[NMAX];
vector < pair <int, int> > graph[NMAX];


void read_data () {
	
	cin >> N >> M;	

	for (int i = 1; i <= N; i++)
		graph[i].clear ();
                          
	int x, y, z;
	for (int i = 1; i <= M; i++) {
		cin >> x >> y >> z;
		graph[x].push_back ( make_pair (y, z) ); 
		graph[y].push_back ( make_pair (x, z) );
	} 
}

void prim () {

	memset (cost, INF, sizeof (cost));
	memset (use, 0, sizeof (use));
    memset (parent, 0, sizeof (parent));

	int node;
	int M[NMAX];
	memset (M, 0, sizeof (M));        
	
	int curr_cost;
	long long min_cost = 0;

	for (int i = 1; i <= N; i++)
		if (!use[i]) {
			cost[i] = 0; parent[i] = 0;
			
			while (1 == 1) {
				
				node = 0, curr_cost = INF;
                for (int i = 1; i <= N;  i++)
					if (!use[i] && cost[i] < curr_cost) {
						curr_cost = cost[i];
						node = i;
					}

				if (curr_cost == INF)
					break;

                min_cost+= (long long) curr_cost;
                use[node] = 1;

				for (vector < pair <int, int> >::iterator it = graph[node].begin (); it != graph[node].end (); it++) 
					if (!use[it->first] && cost[it->first] > it->second) {
						parent[it->first] = node;
						cost[it->first] = it->second;
					}
			}

		}

	cout << min_cost << endl;
	cout << N - 1 << endl;
	for (int i = 1; i <= N; i++)
		if (parent[i])
			cout << parent[i] << ' ' << i << endl;
}

int main () {                          

	freopen ("apm.in", "r", stdin);
	freopen ("apm.out", "w", stdout);
	
	read_data ();
	prim ();

	return 0;
}