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

using namespace std;

ifstream in("../apm.in");
ofstream out("../apm.out");


const int NMAX = 200005;

int n, m;
int suma = 0;
int viz[NMAX];


struct edge
{
	int x, y, cost;
};

struct cmp
{
	bool operator() (const edge &a, const edge &b)
	{
		return a.cost > b. cost;
	}
};

vector <edge> graf[NMAX];
vector <edge> Sol;

priority_queue <edge, vector <edge>, cmp > heap;

void citire()
{
	in >> n >> m;
	for(int i = 0; i < m; i++)
	{
		edge muchie;
		in >> muchie.x >> muchie.y >> muchie.cost;
		graf[muchie.x].push_back(muchie);
	}
}

void adauga(int nod)
{
	for(auto e : graf[nod])
	{
		if(viz[e.y] == 0)
			heap.push(e);
	}
}

void solve()
{
	viz[1] = 1;
	adauga(1);
	int nr = 1;
	while(nr != n - 1)
	{
		edge muchie = heap.top();
		heap.pop();
		if(viz[muchie.y] == 0)
		{
			viz[muchie.y] = 1;
			adauga(muchie.y);
			Sol.push_back(muchie);
			nr++;
			suma += muchie.cost;
		}
	}
}
int main()
{
	citire();
	solve();
	out << suma << "\n";
	out << Sol.size()<< "\n";
	for(auto e : Sol)
	{
		out << e.x << " " << e.y << "\n";
	}
	return 0;
}