#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>

const int NMAX = 2e5 + 5;
const int INF = 1<<29;

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

vector < pair < int, int > > g[NMAX];
set < pair < int, int > > heap;

int t[NMAX];
int d[NMAX];
int use[NMAX];

long long s;

int n, m;

int main(){
	fin >> n >> m;
	while(m--){
		int a, b, c;
		fin >> a >> b >> c;
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}
	for(int i = 2; i <= n; i++)
		d[i] = INF;
	heap.insert({0, 1});
	while(!heap.empty()){
		auto h = *heap.begin();
		heap.erase(heap.begin());
		if(use[h.second])
			continue;
		use[h.second] = 1;
		for(auto i : g[h.second]){
			if(use[i.first])
				continue;
			if(d[i.first] > i.second){
				d[i.first] = i.second;
				t[i.first] = h.second;
				heap.insert({d[i.first], i.first});
			}
		}
	}
	for(int i = 1; i <= n; i++)
		s+= d[i];
	fout << s << '\n' << n - 1 << '\n';
	for(int i = 2; i <= n; i++)
		fout << i << ' ' << t[i] << '\n';
	return 0;
}