#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define MAXN 0x7fffffff
using namespace std;

int map[1010][1010],ml,len[1010];
int vex[1010][2],top;
bool sta[1010];

void init(int n)
{
	top=ml=0;
	//tmin=MAXN;
	for (int i=0;i<=n;i++)
	{
		for (int j=0;j<=n;j++)
			map[i][j]=MAXN;
		len[i]=MAXN;
	}
	memset(sta,0,sizeof(sta));
}

void prim(int n)
{
	sta[1]=1;
	len[1]=0;
	for (int i=2;i<=n;i++)
	{
		len[i]=map[1][i];
	}
	int s=1,id=1,smin=MAXN;
	for (int i=2;i<=n;i++)
	{
		smin=MAXN;
		for (int j=1;j<=n;j++)
			if(!sta[j]&&map[s][j]<smin)
			{
				smin=map[s][j];
				id=j;
			}
		vex[top][0]=s;
		vex[top++][1]=id;
		sta[id]=true;
		s=id;
		for (int j=1;j<=n;j++)
		{
			if(!sta[j]&&map[s][j]<len[j])
				len[j]=map[s][j];
		}		
	}
	
	//int res=0;
	ml=len[1];
	//printf ("ml :%d \n",ml);
	//printf ("----------------\n");
	for (int i=2;i<=n;i++)
	{
	//	printf ("%d ",len[i]);
		if(ml<len[i])
			ml=len[i];
		//res+=len[i];
	}
//	printf ("\n");
	return ;
}

int main()
{
	int n,m;
	while (scanf ("%d %d",&n,&m)!=EOF)
	{
		int x,y,val;
		init(n);
		for (int i=0;i<m;i++)
		{
			scanf ("%d %d %d",&x,&y,&val);
			map[x][y]=map[x][y]<val?map[x][y]:val;
			map[y][x]=map[x][y];
		}
		prim(n);
		printf ("%d\n%d\n",ml,top);
		for (int i=0;i<top;i++)
			printf ("%d %d\n",min(vex[i][0],vex[i][1]),max(vex[i][0],vex[i][1]));///感觉输出的变的顺序是不是小号在前面，所以改了一下~
	}
}