#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

typedef struct muchie
{int x,y,c;};
muchie a[200001];
vector<int>sol;
int n,m,c[200001],cost;


bool cmp(const muchie l,const muchie r)
{return l.c<r.c;}

void read()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
	scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
for(int i=1;i<=n;i++)
	c[i]=i;
}


void solve()
{
int min,max;
sort(&a[1],&a[m+1],cmp);

for(int i=1;sol.size()<n-1;i++)
	if(c[a[i].x]!=c[a[i].y])
	{sol.push_back(i);
	cost+=a[i].c;
	if(c[a[i].x]<c[a[i].y])
	{min=c[a[i].x];
	max=c[a[i].y];}
	else
	{min=c[a[i].y];
	max=c[a[i].x];}
	for(int j=1;j<=n;j++)
		if(c[j]==max)c[j]=min;
	}

vector<int>::iterator it;

printf("%d\n%d\n",cost,sol.size());

for(it=sol.begin();it!=sol.end();it++)
	printf("%d %d\n",a[*it].y,a[*it].x);
}


int main()
{freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
read();
solve();
return 0;}