#include<iostream>
#include<fstream>
#include<algorithm>
#include<set>
#include<map>
#include<numeric>
#include<unordered_set>
#include<unordered_map>
#include<vector>
#include<stack>
#include<queue>
#include<limits>
#define all(v) v.begin(),v.end()
#define sorti(v) sort(all(v))
#define desc(x) greater<x>()
#define lsb(x) ((x)&(-x))
#define sortd(v) sort(all(v),desc(decltype(v[0])))
#define hmap unordered_map 
#define var auto&
#define hset unordered_set
#define pq priority_queue
#define inf 0x3f3f3f3f
#define exists(x,v) (v.find(x)!=v.end())
#define inrange(x,a,b) (x>=a && x<=b)
using namespace std;
typedef long long ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long, long> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
template<typename T> T gcd(T a, T b) { T c; while (b) { c = a % b; a = b; b = c; }return a; }
template<typename T> T exp(T a, T n, T m) { T p = 1; while (n) { if (n & 1)p = (p % m * a % m) % m; a = (a % m * a % m) % m; n >>= 1; }return p; }
template<typename T> T exp(T a, T n){T p = 1; while (n) { if (n & 1)p *= a; a *= a;  n >>= 1; }return p;}
template<typename T> T invm(T a, T m) {return exp(a, m - 2, m);}
const int lim = 2e5;
vector<pii> graph[lim];
int n, m;
struct cmp {
	bool operator()(pii a, pii b)
	{
		return a.first > b.first;
	}
};
pq<pii,vector<pii>,cmp> q;
int ans;
bool vis[lim];
int t[lim];
int dist[lim];
int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, c;
		cin >> x >> y >> c;
		graph[x].push_back({ y,c });
		graph[y].push_back({ x,c });
	}
	for (int i = 1; i <= n; i++)
		dist[i] = inf;

	dist[1] = 0;
	q.push({ 0,1 });
	while (!q.empty())
	{
		int curentWeight = q.top().first;
		int curentNode = q.top().second;
		q.pop();
		if (!vis[curentNode])
		{
			ans += curentWeight;
			vis[curentNode] = true;
			for (auto it : graph[curentNode])
			{
				int v = it.first;
				int c = it.second;
				if (!vis[v] && dist[v] > c)
				{
					dist[v] = c;
					q.push({ dist[v], v });
					t[v] = curentNode;
				}
			}
		}
		
	}
	cout << ans << '\n' << n - 1 << '\n';
	for (int i = 2; i <= n; i++)
		cout << i << " " << t[i] << '\n';
}