#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;
vector<int> v[200002];
pair<int,pair<int,int>> V[400002];
int a[200002];
void fil(int nr)
{
   if(a[nr])return;
   a[nr]=1;
   for(auto it:v[nr])fil(it);
}
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;
   sort(V,V+m);
   nr=n-1;
   for(i=0;i<m&&nr;i++)
   {
      memset(a,0,sizeof(a));
      fil(V[i].y.x);
      if(!a[V[i].y.y])
      {
	 nr--;
	 v[V[i].y.x].push_back(V[i].y.y);
	 v[V[i].y.y].push_back(V[i].y.x);
	 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;
}