#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];

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() {
  coada.push(make_pair(0, 1));
  tata[1] = 0;
  int nr = 0;

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

    coada.pop();

    if(viz[nod]) continue;

    total += cost;

    viz[nod] = 1;
    apm.push_back({nod, tata[nod]});

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

    nr++;
  }
}

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

  citire();
  prim();

  printf("%d\n%d\n", total, apm.size() - 1);
  for(int i = 1; i < apm.size(); i++) {
    printf("%d %d\n", apm[i].first, apm[i].second);
  }

  return 0;
}