#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,niv[200001];


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

int tata(int nod)
{
while(c[nod]!=nod)
	nod=c[nod];
return nod;}


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,x1,y1;
sort(&a[1],&a[m+1],cmp);

for(int i=1;sol.size()<n-1;i++)
	{
	x1=tata(a[i].x);
	y1=tata(a[i].y);
	if(x1!=y1)
		{sol.push_back(i);
		cost+=a[i].c;
		if(niv[x1]>niv[y1])
			c[y1]=x1;
		if(niv[x1]<niv[y1])
			c[x1]=y1;
		if(niv[x1]==niv[y1])
			c[y1]=x1,niv[x1]++;
	
		}
	}

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;}