// lab2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
//kruskal ; complexitate(mlogn)
//folosing alg union, find

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax=100;
int parent[nmax],rang[nmax];
ifstream f("graf.txt");

struct M {
  int x, y, cost;
}graf[nmax];

int m, n, total, k;
pair <int, int> P[nmax];

bool Compare(M a, M b)
{
  return a.cost < b.cost;
}

void Read()
{
  f >> m >> n;
  for (int i = 1; i <= m; i++)
  {
    f >> graf[i].x >> graf[i].y >> graf[i].cost;
  }
  sort(graf + 1, graf + m + 1, Compare);
  for (int i = 1; i <=n; i++)
  {
    parent[i] = i;
    rang[i] = 0;
  }
}

int find(int Nod)
{
  while (parent[Nod] != Nod)
  {
    Nod = parent[Nod];
  }
  return Nod;
}
void unite(int x,int y)
{
  if (rang[x] < rang[y])
    parent[x] = y;
  if (rang[x] > rang[y])
    parent[y] = x;
  if (rang[x] == rang[y])
  {
    parent[x] = y;
    rang[y]++;
  }

}
void kruskal()
{
  for (int i = 1; i <= m; i++)
  {
    if (find(graf[i].x) != find(graf[i].y))
      unite(graf[i].x, graf[i].y);
    P[++k].first = graf[i].x;
    P[k].second = graf[i].y;
    total += graf[i].cost;
  }
}
int main()
{
  Read();
  kruskal();
  cout << total << "\n";
  cout << n - 1 << "\n";
  for (int i = 1; i <= k; i++)
    cout << P[i].first << " " << P[i].second << "\n";
  return 0;

}