#include <bits/stdc++.h>
using namespace std;

namespace APM {
	struct edge {
		int x, y;
		int c; ///avem grija la tipul costurilor muchilor

		bool operator < (const edge &aux) const {
			return c < aux.c;
		}
	};

	struct DSU {
		vector <int> tt, sz;
		
		DSU(int n) {
			tt.resize(n + 1);
			sz.resize(n + 1);

			for (int i = 1; i <= n ; ++i) {
				tt[i] = i;
				sz[i] = 1;
			}
		}

		int find(int x) {
			if (x != tt[x]) return (tt[x] = find(tt[x]));
			return x;
		}

		void unite(int x, int y) {
			x = find(x); y = find(y);
			if (x == y) return ;

			if (sz[x] < sz[y]) swap(x, y);
			tt[y] = x;
			sz[x] += sz[y];
		}
	};

	int n, m;
	vector <edge> a;

	void citire() {
		scanf("%d%d", &n, &m);
		a.resize(m);
		for (int i = 0; i < m ; ++i) 
			scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].c);
	}

	///grija la suma nodurilor si daca avem nevoie sa retinem muchiile sau nu
	void solve() {
		DSU arb(n);
		sort(a.begin(), a.end());
		int ans = 0;
		vector <pair <int, int>> afis;

		for (auto it : a) {
			///it.x si it.y fac parte din aceeasi componenta			
			if (arb.find(it.x) != arb.find(it.y)) {
				arb.unite(it.x, it.y);
				ans = ans + it.c;
				afis.push_back({it.x, it.y});
			}
		}
		
		printf("%d\n", ans);
		printf("%d\n", (int)afis.size());
		for (auto it : afis) printf("%d %d\n", it.first, it.second);

		//return ans;
	}
}

int main() {
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	APM::citire();
	APM::solve();

	return 0;
}