#include<stdio.h>
#include<vector>
#include<algorithm>
#define inf "apm.in"
#define outf "apm.out"
#define NMax 200100
#define INF 0x3f3f3f3f
using namespace std;

vector< pair<int,int> > LA[NMax],apm;
int result;
int N,M;
int S[NMax],dist[NMax];
int H[NMax],poz[NMax],hdim;

void read()
{
int x,y,c;
scanf("%d%d",&N,&M);
for(int i=1; i<=M; i++)
	{
	scanf("%d%d%d",&x,&y,&c);
	LA[x].push_back( make_pair(y,c) );
	LA[y].push_back( make_pair(x,c) );
	}
}

void upheap(int nod)
{
int father;
while( nod>1 )
	{
	father = nod>>1;
	if( father && dist[ H[father] ] > dist[ H[nod] ] )
		{
		swap( poz[ H[father] ], poz[ H[nod] ] );
		swap( H[father] , H[nod] );
		nod = father;
		}
	else return;
	}
}

void downheap(int nod)
{
int son;
while( nod<=hdim )
	{
	son = nod<<1;
	if( son<=hdim )
		{
		if( son+1<=hdim && dist[ H[son+1] ] < dist[ H[son] ] ) son++;
		if( dist[ H[son] ] < dist[ H[nod] ] )
			{
			swap( poz[ H[son] ] , poz[ H[nod] ] );
			swap( H[son], H[nod] );
			nod = son;
			}			
		else return;
		}
	else return;
	}
}

int extract_min()
{
int x=H[1];
swap( poz[ H[1] ] , poz[ H[hdim] ] );
swap( H[1],H[hdim] );
hdim--;
downheap(1);
poz[x]=0;
return x;
}

void add_heap(int x)
{
hdim++;
H[hdim]=x;
poz[x]=hdim;
upheap(hdim);
}

void add_apm(int x)
{
int nod,cost;
for(unsigned int i=0; i<LA[x].size(); i++)
	{
	nod = LA[x][i].first;
	cost = LA[x][i].second;
	dist[nod] = min( dist[nod], cost );
	if( dist[nod]==cost ) S[nod]=x;
	}
}

void solve()
{
//init
for(int i=2; i<=N; i++) dist[i]=INF;
dist[1]=0;
//init
add_apm(1);
for(int i=2; i<=N; i++) add_heap(i);

int x;
for(int i=1; i<N; i++)
	{
	x = extract_min();
	add_apm(x);
	result += dist[x];
	apm.push_back( make_pair(x,S[x]) );
	for(unsigned int j=0; j<LA[x].size(); j++)
		{
		int nod = LA[x][j].first;
		if( poz[nod] ) upheap(poz[nod]);
		}
	}
printf("%d\n%d\n",result,N-1);
for(unsigned int i=0; i<apm.size(); i++) printf("%d %d\n",apm[i].first,apm[i].second);
}

int main()
{
freopen(inf,"r",stdin);
freopen(outf,"w",stdout);
read(); solve();
return 0;
}