#include<iostream>
#include<fstream>
#include <list>
#include<vector>
#include<queue>
#define inf 1001
using namespace std;

struct edge {
	int w, x, y; // w-> weight; xy -> capetele muchiei
};

list<pair<int, int> > T; //lista cu muchiile din APM
vector<list<pair< int, int> > > Neighbours;//Listele de vecini, pereche de tip cost, nod (!!!);
int cost;//costul total;
int n, m;// nr de noduri, nr de muchii;
priority_queue < pair<int, int >, vector<pair<int, int> >, greater<pair<int, int> > > Q;
bool* sel;//vector caracteristic pentru noduri (ne)selectate
int* dist;//aici vom tine minte pentru fiecare nod ponderea muchiei de cost minim de la el la un nod selectat; 
int* tata;//tatal nodului curent selectat in APM
int no_of_selected = 0; //numarul de noduri selectate; 

int main()
{
	ifstream fin("apm.in");
	fin >> n >> m;
	Neighbours.resize(n + 1); //alocam dimensiune pentru vectorul de liste de vecini
	sel = new bool[n + 1];
	dist = new int[n + 1];
	tata = new int[n + 1];

	for (int i = 1; i <= n; i++)
	{
		sel[i] = false;//initial toate nodurile sunt neselectate; 
		dist[i] = inf;
		tata[i] = -1;
	}

	for (int i = 0; i < m; i++)
	{
		int x, y, w;
		fin >> x >> y >> w; //citim muchia xy cu pondere w
		Neighbours[x].push_back({ w,y });// adaugam pe y cu ponderea w in lista vecinilor lui x. Important ca ponderea sa fie prima componenta. Ajuta la implementarea sortarii
		Neighbours[y].push_back({ w,x });// analog
	}

	int start; //nodul de start
	start = 1; //cin>>start;
	dist[start] = 0;
	tata[start] = 0;
	Q.push({ dist[start],start }); 
	while (!Q.empty())
	{
		int myNode = Q.top().second;
		int w = Q.top().first;
		Q.pop();
		if (sel[myNode]) continue; 
		sel[myNode] = true; no_of_selected++;
		if (tata[myNode] != 0)
		{
			T.push_back({ myNode,tata[myNode] });
			cost += dist[myNode];
		}
		if (no_of_selected == n) break;

		for (auto k : Neighbours[myNode])
		{
			if (!sel[k.second] && k.first < dist[k.second])
			{
				tata[k.second] = myNode;
				dist[k.second] = k.first;
				Q.push({k});
			}
		}
	}

	ofstream fout("apm.out");

	fout << cost; 
	fout << endl << T.size() << endl;
	for (auto p : T) {
		fout << p.first << " " << p.second << endl;
	}
	
	fin.close();
	fout.close();

	return 0;
}