#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
vector<pair<int,int>> va;
pair<int,pair<int,int>> v[400002];
int g[200002];
int gr(int nr)
{
   if(g[nr]==nr)return nr;
   g[nr]=gr(g[nr]);
   return g[nr];
}
int main()
{
   int n,m,i,nr,nr1,nr2,s=0;
   in>>n>>m;
   for(i=0;i<m;i++)
      in>>v[i].y.x>>v[i].y.y>>v[i].x;
   for(i=1;i<=n;i++)
      g[i]=i;
   sort(v,v+m);
   for(i=0;i<m;i++)
   {
      if(gr(v[i].y.x)!=gr(v[i].y.y))
      {
	 g[gr(v[i].y.x)]=gr(v[i].y.y);
	 s+=v[i].x;
	 va.push_back(v[i].y);
      }
   }
   out<<s<<"\n"<<n-1<<"\n";
   for(i=0;i<n-1;i++)
      out<<va[i].x<<" "<<va[i].y<<"\n";
   return 0;
}