#include <bits/stdc++.h>
using namespace std;

#define MAXN 200001

int n, m, total;
vector<pair<int, int> >graf[MAXN];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int> > > coada;
bitset<MAXN> viz;
vector<pair<int, int> > apm;
int tata[MAXN];

int best[MAXN];

void citire() {
  scanf("%d %d ", &n, &m);
  for(int i = 1; i <= m; i++) {
    int x, y, cost;
    scanf("%d %d %d ", &x, &y, &cost);
    graf[x].push_back({y, cost});
    graf[y].push_back({x, cost});
  }
}

void prim() {
  fill(best, best + n + 1, 0x3f3f3f3f);

  coada.push(make_pair(0, 1));

  while(!coada.empty()) {
    int nod = coada.top().second;

    coada.pop();

    if(viz[nod]) continue;

    viz[nod] = 1;

    for(auto it : graf[nod]) {
      if(!viz[it.first] && it.second < best[it.first]) {
        tata[it.first] = nod;
        coada.push({it.second, it.first});
        best[it.first] = it.second;
      }
    }
  }
}

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

  citire();
  prim();

  for(int i = 2; i <= n; i++) 
    total += best[i];

  printf("%d\n%d\n", total, n - 1);

  for(int i = 2; i <= n; i++) {
    printf("%d %d\n", i, tata[i]); 
  }

  return 0;
}