#define DM 400001
#define DN 200001
#include <bitset>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

ifstream fi ("apm.in");
ofstream fo ("apm.out");
bitset <DM> bs;
int n, k, a, b, c, val[DN], s;	
priority_queue <pair <int, pair <int, int> > > pq;
queue <pair <int, int> > q;
vector <pair <int, int> > v[DN];

int main()
{
	fi >> n >> k;
	for (int i = 1; i <= k; ++i)
	{
		fi >> a >> b >> c;
		v[a].push_back(make_pair(b, c));
		v[b].push_back(make_pair(a, c));
	}
	bs[1] = 1;
	for (int i = 0; i < v[1].size(); ++i)
		pq.push(make_pair(-v[1][i].second, make_pair(1, v[1][i].first)));
	while (!pq.empty())
	{
		if (!bs[pq.top().second.second])
		{
			a = pq.top().second.first, b = pq.top().second.second, c = -pq.top().first;
			pq.pop();
			val[b] = val[a] + c;
			bs[b] = 1;
			for (int i = 0; i < v[b].size(); ++ i)
				if (!val[v[b][i].first] && v[b][i].first != 1)
				pq.push(make_pair(-v[b][i].second, make_pair(b, v[b][i].first)));
			q.push(make_pair(a, b));
			s+=c;
		}
		else
			pq.pop();
	}
	fo << s << '\n' << n - 1 << '\n';
	while (!q.empty())
	{
		fo << q.front().first << ' ' << q.front().second << '\n';
		q.pop();
	}
	return 0;
}