//#include "stdafx.h"
#include<stdio.h>
#include<vector>
#include<set>
#include<queue>
#define NMAX 200100
#define inf 1001000
using namespace std;
vector <int> x[NMAX],y[NMAX];
set <pair < int , int > > dist;
vector <pair < int, int> > w;
int viz[NMAX],k,rez,i,j,a,b,c,n,m,nod,d[NMAX];
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
		d[i]=inf;
	for (i=1;i<=m;i++)
	{
			scanf("%d%d%d",&a,&b,&c);
			if (a==1)
			{
				dist.insert(make_pair(c,b));
				d[b]=c;
			}
			if (b==1)
			{
				dist.insert(make_pair(c,a));
				d[a]=c;
			}
			x[a].push_back(b);
			x[b].push_back(a);
			y[a].push_back(c);
			y[b].push_back(c);
	}
	
	viz[1]=1;
	j=2;
	for (;j<=n;)
	{
		nod=dist.begin()->second;
		if (!viz[nod])
		{
			k=dist.begin()->first;
			dist.erase(dist.begin());
			rez+=k;
			j++;
			viz[nod]=1;
			for (i=0;i<x[nod].size();i++)
				if (y[nod][i]==k)
				{
					w.push_back(make_pair(nod,x[nod][i]));
					i=x[nod].size();
				}
			for (i=0;i<x[nod].size();i++)
				if (y[nod][i]<d[x[nod][i]])
				{
					d[x[nod][i]]=y[nod][i];
					dist.insert(make_pair(y[nod][i],x[nod][i]));
				}

		}
		else
			dist.erase(dist.begin());
	}
	printf("%d\n%d\n",rez,w.size());
	for (i=0;i<w.size();i++)
		printf("%d %d\n",w[i].first,w[i].second);
}