#include <fstream>
#include <algorithm>
#include <vector>
#include <map>
#include <cstring>
#include <set>
#define max(a,b) ((a>b) ? (a) : (b))
#define min(a,b) ((a<b) ? (a) : (b))
#define pb push_back
#define mp make_pair
#define ll long long
#define INF 1e9+7
#define fi first
#define se second

using namespace std;

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

int n, m, cost, tata[200005], uz[200005];
vector<pair<int,int> > L[200005];
set<pair<int, pair<int,int> > > S;

int main()
{
	int i, j, x, y, c;

	fin >> n >> m;
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y >> c;
		L[x].pb(mp(y, c));
		L[y].pb(mp(x, c));
	}
	tata[1] = 0;
	uz[1] = 1;
	for (i = 0; i < L[1].size(); i++)
		S.insert(mp(L[1][i].se, mp(1,L[1][i].fi)));
	for (i = 2; i <= n; i++)
	{
		while (uz[(*S.begin()).se.se])
			S.erase(S.begin());
		auto aux = (*S.begin());
		tata[aux.se.se] = aux.se.fi;
		cost += aux.fi;
		uz[aux.se.se] = 1;
		for (j = 0; j < L[aux.se.se].size(); j++)
		{
			auto nod = L[aux.se.se][j];
			S.insert(mp(nod.se, mp(aux.se.se, nod.fi)));
		}
	}
	fout << cost << '\n' << n-1 << '\n';
	for (i = 2; i <= n; i++)
		fout << i << ' ' << tata[i] << '\n';
	return 0;
}