#include <fstream>
#include <vector>
#include <queue>

#define DIM 200010
#define x first
#define y second.first
#define z second.second
#define INF (1 << 30)

using namespace std;

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

int n, m;
int dp[DIM];

bool vis[DIM];

vector<int> apmEdges;

vector< pair< int, pair<int, int> > > L[DIM];

pair< int, pair<int, int> > edges[2 * DIM];

struct cmp {

	bool operator()(const pair< int, pair<int, int> > &a, const pair< int, pair<int, int> > &b) {

		return a.z > b.z;

	}

};

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

int main() {

	fin >> n >> m;

	for (int i = 1; i <= m; i++) {

		int cost;

		fin >> edges[i].x >> edges[i].y >> cost;

		L[edges[i].x].push_back(make_pair(edges[i].y, make_pair(i, cost)));
		L[edges[i].y].push_back(make_pair(edges[i].x, make_pair(i, cost)));

	}

	for (int i = 2; i <= n; i++)
		dp[i] = INF;

	int solution = 0;

	H.push(make_pair(1, make_pair(-1, 0)));

	while (!H.empty()) {

		int node = H.top().x;
		int edge = H.top().y;
		int cost = H.top().z;

		H.pop();

		if (vis[node])
			continue;

		vis[node] = true;

		if (edge != -1)
			apmEdges.push_back(edge);
		solution += cost;

		for (int i = 0; i < L[node].size(); i++) {

			int child = L[node][i].x;
			int childEdge = L[node][i].y;
			int childCost = L[node][i].z;

			if (dp[child] > childCost) {

				H.push(make_pair(child, make_pair(childEdge, childCost)));
				dp[child] = childCost;

			}

		}

	}

	fout << solution << "\n" << apmEdges.size() << "\n";

	for (int i = 0; i < apmEdges.size(); i++)
		fout << edges[apmEdges[i]].x << " " << edges[apmEdges[i]].y << "\n";

	return 0;

}

//Miriam e tare!