#include<fstream>
#include<vector>
#include<iostream>
#include<chrono>
#include<queue>
#include<algorithm>
using namespace std;

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

struct Node
{
	int x, w, i;

	Node(int x, int w, int i)
	{
		this->x = x;
		this->w = w;
		this->i = i;
	}

};

struct comparator
{
	bool operator () (const Node &e1, const Node &e2)
	{
		return e1.w > e2.w;
	}
};

priority_queue<Node, vector<Node>, comparator> PQ;

vector<Node> G[200010],Edges;

int d[200010];
int used[200010];

int main()
{
	int N, M;
	in >> N >> M;

	Edges.push_back(Node(0, 1<<31, 0));

	for (int i = 1; i <= M; ++i)
	{
		int x, y, w;
		in >> x >> y >> w;
		Edges.push_back(Node(x, w, y));

		G[x].push_back(Node(y,w,i));
		G[y].push_back(Node(x,w,i));
	}
	
	Edges.push_back(Node(0, 1 << 30,0));
	for (int i = 1; i <= N; ++i)
		d[i] = Edges.size() - 1;

	d[1] = 0;

	PQ.push(Node(1, 1<<31, 0));

	while (PQ.size())
	{
		Node x = PQ.top();

		PQ.pop();

		used[d[x.x]] = 1;

		if (x.w > Edges[d[x.x]].w)
			continue;

		for (int i = 0; i < G[x.x].size(); ++i)
		{
			if (!used[G[x.x][i].i] && !used[d[G[x.x][i].x]] && G[x.x][i].w < Edges[d[G[x.x][i].x]].w)
			{
				d[G[x.x][i].x] = G[x.x][i].i;
				PQ.push(Node(G[x.x][i].x, G[x.x][i].w, 0));
			}
		}

	}
	int c = 0;
	for (int i = 2; i <= N; ++i)
	{
		c += Edges[d[i]].w;
	}
	
	out << c<<"\n"<< N - 1 << "\n";

	for (int i = 2; i <= N; ++i)
	{
		out << Edges[d[i]].x << " " << Edges[d[i]].i << "\n";
	}
	
	
	

	return 0;
}