//Prim's

#include <bits/stdc++.h>

using namespace std;

FILE *in = fopen("apm.in", "r");
ofstream out("apm.out");

vector< pair<int, int> > graf[200000 + 7];
int heap[4*200000 + 7];
bool used[200000 + 7];
int total = -2000;
int from[200000+7];

const int pow2 = (1<<18);
const int INF_0 = 3000;
const int INF_1 = 6000;

void setup()
{
	for(int i = 1; i < 2*pow2; i++)
	{
		heap[i] = INF_0;
	}
}

int get_min()
{
	int index = 1;
	do
	{
		
		index *= 2;
		if(heap[index + 1] < heap[index])
			index += 1;
	
	} while(index < pow2);
	
	return index - pow2;
}

void heap_update(int p, int val)
{
	int index = pow2 + p;
	
	heap[index] = val;
	
	do
	{
		index /= 2;
		heap[index] = min(heap[2*index], heap[2*index + 1]);
	}while(index > 1);
}

void update(int p)
{
    
	total += heap[pow2 + p] - 1000;
	
	used[p] = 1;
	
	heap_update(p, INF_1);
	
	for(int i = 0; i < graf[p].size(); i++)
	{
		int other_p = graf[p][i].first;
		if(used[other_p] == 0 && heap[pow2 + other_p] > graf[p][i].second)
		{
			heap_update(other_p, graf[p][i].second);
			from[other_p] = p;
		}
	}
}

int main()
{
	int n, m;
	fscanf(in, "%d", &n);
	fscanf(in, "%d", &m);
	
	setup();
	
	int u, v, c;
	for(int i = 0; i < m; i++)
	{
		fscanf(in, "%d", &u);
		fscanf(in, "%d", &v);
		fscanf(in, "%d", &c);
		u--;
		v--;
		c += 1000;
	
		graf[u].push_back(make_pair(v, c));
		graf[v].push_back(make_pair(u, c));
	}
	
	for(int i = 0; i < n; i++)
	{
	    //cout << get_min() << " " << heap[pow2 + get_min()] << endl;
		update(get_min());
	}
	
	out << total << endl;
	
	out << n-1 << endl;
	
	for(int i = 1; i < n; i++)
	{
		out << from[i]+1 << " " << i+1 << endl;
	}
	
	return 0;
}