#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define INF 1000000000

using namespace std;

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

int n, m;
vector < pair < int, int > > G[100008];
vector < pair < int, int > > Rez;
int cmin[100008];
int F[100008];
int sum_max;
int noduri;

struct cmp
{
	bool operator()(pair < pair < int, int >, int > a, pair < pair < int, int >, int > b) {
		if (a.second > b.second)
			return 1;
		return 0;
	}
};

priority_queue < pair < pair < int, int >, int >, vector < pair < pair < int, int >, int > >, cmp > Q;



int main() {

	int x, y, c;
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		fin >> x >> y >> c;
		G[x].push_back(make_pair(y, c));
		G[y].push_back(make_pair(x, c));
	}

	int start = 1;

	for (int i = 1; i <= n; i++)
		cmin[i] = INF;
	cmin[start] = 0;

	Q.push(make_pair(make_pair( 1, 0 ), 0));
	while (!Q.empty() && noduri < n) {

		int nod = Q.top().first.first;
		int prec = Q.top().first.second;
		int c = Q.top().second;
		Q.pop();


		if (F[nod] == 1)
			continue;

		F[nod] = 1;
		cmin[nod] = c;
		Rez.push_back(make_pair(nod, prec));
		noduri++;
		

		for (int i = 0; i < G[nod].size(); i++) {
			Q.push(make_pair(make_pair(G[nod][i].first, nod), G[nod][i].second));
		}

	}

	for (int i = 1; i <= n; i++)
		sum_max += cmin[i];

	fout << sum_max << '\n';
	fout << Rez.size() - 1 << '\n';
	for (int i = 1; i < Rez.size(); i++)
		fout << Rez[i].first << ' ' << Rez[i].second << '\n';
	



}