//kruskal cu multimi disjuncte
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

FILE*fin=fopen("apm.in","r");
FILE*fout=fopen("apm.out","w");
#define c first
#define a second.first
#define b second.second
#define mkp make_pair
#define mm 400001
#define nm 200001
int n,father[nm],g[nm],m;
vector < pair<int,pair<int,int> > > edges,used_edges;

int find(int x)
{
  int y=x,ans;
  while(father[x]!=x) x=father[x];
  ans=x;
  while(y!=ans)
  {
    x=father[y];
    father[y]=ans;
    y=x;
  }
  return ans;
}
void unite(int x,int y)
{
  if(g[x]>g[y]) father[y]=x;
  else father[x]=y;
  if(g[x]==g[y]) g[y]++;
}
int main()
{
  int i,ue=0,ans=0,fx,fy,x,y,z;
  fscanf(fin,"%d%d",&n,&m);
  for(i=1;i<=m;i++)
  {
    fscanf(fin,"%d%d%d",&x,&y,&z);
    edges.push_back(mkp(z,mkp(x,y)));
  }
  for(i=1;i<=n;i++)
  {
    father[i]=i;
    g[i]=1;
  }
  sort(edges.begin(),edges.end());
  i=0;
  for(;i<m&&ue<n-1;i++)
    {
      x=edges[i].a;
      y=edges[i].b;
      z=edges[i].c;
      fx=find(x);fy=find(y);
      if(fx!=fy)
      {
	ue++;
	used_edges.push_back(mkp(z,mkp(x,y)));
	ans+=z;
	unite(fx,fy);
      }
    }
  fprintf(fout,"%d\n%d\n",ans,n-1);
  for(i=0;i<n-1;i++)
    fprintf(fout,"%d %d\n",used_edges[i].a,used_edges[i].b);
  fclose(fin);
  fclose(fout);
  return 0;
}