#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,  m, tata[105], rang[105];

 struct muchie
 {
    int cost, a, b;
 };
 vector<muchie> graf;
 vector< pair<int, int> > v;
 bool cmp(muchie a, muchie b)
 {
 return a.cost < b.cost;
 }
void citire()
{
   f>>n>>m;
   muchie var;
   for(int i=1;i<=m;++i)
   {
     f>>var.a>>var.b>>var.cost;
     graf.push_back(var);
   }
   for(int i=1;i<=n;++i) tata[i] = i;
}
int parinte(int n)
{
   while(tata[n] != n) n = tata[n];
   return n;
}
void uneste(int x, int y)
{
    if (rang[x] < rang[y]) tata[x] = y;
       else if(rang[x] > rang[y]) tata[y] = x;
          else {
        tata[x]=y;
        rang[y]++;
        }
 }
 int suma, cnt;
 void solutie()
 {
     for( int i=0;i<graf.size();++i)
     {
        int tata_x = parinte(graf[i].a);
        int tata_y = parinte(graf[i].b);
    if(tata_x != tata_y)
    {
   uneste(tata_x, tata_y);
   cnt++;
   v.push_back(make_pair(graf[i].a, graf[i].b));
    suma+=graf[i].cost;
    }
     }
 }
int main()
{
  citire();
     sort(graf.begin(), graf.begin()+m, cmp);
   solutie();
  g << suma << "\n";
  g << cnt << "\n";
  for(int i=0;i<v.size();++i) {
  g << v[i].first << " " << v[i].second;
  g << "\n";
  }
    return 0;
}