#include <fstream>
#include <set>
#include <vector>
#define st first
#define nd second
#define PB push_back
#define MP make_pair

using namespace std;

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

const int maxn = 200200 , INF = int(2e9);
set<pair<int,int> > h;
vector <pair<int,int> > G[maxn];
int N , M  , nrv , x , y , c ,ans , D[maxn] , T[maxn];
bool ok[maxn];

int main()
{
	fin>>N>>M;
	for(int i = 1;i <= M; ++i)
	{
		fin>>x>>y>>c;
		G[x].PB(MP(y,c));
		G[y].PB(MP(x,c));
	}
	for(int i = 1;i <= N; ++i) D[i] = INF;
	D[1] = 0;
	ok[0] = 1;
	h.insert(MP(0,1));
	for(nrv = N;nrv;)
	{
		for(x = 0;ok[x] && !h.empty();x=(*h.begin()).nd,h.erase(*h.begin()));
		ok[x] = 1;
		ans+=D[x]; 
		nrv--;
		for(int i=0;i<(int)G[x].size();++i)
			if(G[x][i].nd<D[G[x][i].st] && !ok[G[x][i].st])
				T[G[x][i].st] = x, D[G[x][i].st] = G[x][i].nd , h.insert(MP(G[x][i].nd,G[x][i].st));
	}
	fout<<ans<<'\n'<<N-1<<'\n';
	for(int i = 2;i<=N;++i)
		fout<<T[i]<<' '<<i<<'\n';
	return 0;
}