#include<iostream>
#include<algorithm>
using namespace std;
struct tt
{
  int a,b,w;
};
struct tt s[16000];
long f[1010],t[1010][2];
int cmp(struct tt a, struct tt b)
{
  return a.w<b.w;
}
int find(int k)
{
  if (f[k]==k) return k;
  f[k]=find(f[k]);
  return f[k];
}
main()
{ 
  int n,m,i,res,k,w;
  cin>>n>>m;
  for (i=1;i<=n;i++)
    f[i]=i;
  for (i=0;i<=m-1;i++)
    cin>>s[i].a>>s[i].b>>s[i].w;
  sort(s,s+m,cmp);
  res=0; w=0;
  for (i=0;i<=m-1;i++)
    if (find(s[i].a)!=find(s[i].b))
      {
        f[find(s[i].b)]=find(s[i].a);
        if (res<s[i].w)
          res=s[i].w;
        w=w+1;
        t[w][1]=s[i].a; t[w][2]=s[i].b;
      }
  cout<<res<<endl;
  cout<<w<<endl;
  for (i=1;i<=w;i++)
    cout<<t[i][1]<<' '<<t[i][2]<<endl;
}