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

using namespace std;

const int maxn = 200200;
const int INF = int(2e9);

set<pair<int,int> > h;
int  ans , D[maxn] , T[maxn];
vector <pair<int,int> > G[maxn];
int N , M  , nrv , x , y , c ;
bool ok[maxn];

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d %d\n",&N,&M);
	for(int i = 1;i <= M; ++i)
	{
		scanf("%d %d %d",&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));
	}
	printf("%d\n%d\n",ans,N-1);
	for(int i = 2;i<=N; ++i)
		printf("%d %d\n",i,T[i]);
	return 0;
}