#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int NMAX = 200000;
const int CMAX = 1000;

struct elem {
  int nod, cost;

  elem(int cnod = 0, int ccost = 0) {
    nod = cnod;
    cost = ccost;
  }
};

bool operator > (elem e1, elem e2) {
  return e1.cost > e2.cost;
}

int n, m, APM;
vector<elem> graf[NMAX + 5];
priority_queue<elem, vector<elem>, greater<elem>> pq; /// tin nodurile in ordinea crescatoare a cmin
bool sel[NMAX + 5]; /// sel[i] = 1 daca nodul i face parte din APM, 0 daca nu face parte din APM
int cmin[NMAX + 5]; /// cmin[i] = distanta minima dintre nodul i si nodurile din APM
int tata[NMAX + 5]; /// tata[i] = ascendentul direct in APM

int main() {
  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);

  /// citire
  scanf("%d %d", &n, &m);

  for(int i = 1; i <= m; i++) {
    int x, y, c;

    scanf("%d %d %d", &x, &y, &c);

    graf[x].push_back(elem(y, c));
    graf[y].push_back(elem(x, c));
  }

  for(int i = 1; i <= n; i++)
    cmin[i] = CMAX + 5; /// initial niciun nod nu face parte din APM

  cmin[1] = 0; /// adaug nodul 1 la APM
  pq.push(elem(1, 0));

  while(!pq.empty()) {
    elem crt = pq.top(); /// extrag nodul cel mai apropiat de APM
    pq.pop(); /// si il scot din pq
    if(crt.cost > cmin[crt.nod] || sel[crt.nod])
      continue; /// daca nu am cea mai mica valoare pt nod sau a fost deja selectat nu fac nimic

    sel[crt.nod] = true; /// selectez nodul curent
    APM += crt.cost; /// adaug costul la costul total al APM-ului

    /// actualizez distantele pt toti vecinii nodului nou adaugat, in caz ca obtin distante mai mici
    for(elem vec: graf[crt.nod])
      /// daca nodul vecin nu a fost selectat si obtin o distanta mai mica pt el
      /// il adaug in pq, actualizez cmin si tata
      if(!sel[vec.nod] && vec.cost < cmin[vec.nod]) {
        cmin[vec.nod] = vec.cost;
        tata[vec.nod] = crt.nod;
        pq.push(elem(vec.nod, vec.cost));
      }
  }

  /// afisare
  printf("%d\n%d\n", APM, n - 1);
  for(int i = 2; i <= n; i++)
    printf("%d %d\n", tata[i], i);

  return 0;
}