#include <bits/stdc++.h>

using namespace std;

ifstream in ("apm.in");
ofstream out ("apm.out");

typedef pair <int, int> pii;

int n, m;
int x, y, c;
int sol, size;

vector <pii> g[200005];
vector <pii> ans;
int dp[200005], tata[200005], h[500005], in1[500005];

void solve(int nod) {
  for(auto i : g[nod]) {
    dp[i.first] = min(dp[i.first], i.second);
    if(dp[i.first] == i.second)
      tata[i.first] = nod;
  }
}

void heapify(int poz) {
  while((2 * poz <= size && dp[h[poz]] > dp[h[2 * poz]]) || (2 * poz < size && dp[h[poz]] > dp[h[2 * poz + 1]])) {
    if(dp[h[2 * poz]] < dp[h[2 * poz + 1]] || 2 * poz == size) {
      swap(h[poz], h[2 * poz]);
      swap(in1[h[poz]], in1[h[2 * poz]]);
      poz *= 2;
    } else {
      swap(h[poz], h[2 * poz + 1]);
      swap(in1[h[poz]], in1[h[2 * poz + 1]]);
      poz *= 2; poz++;
    }
  }
}

int eraseRoot() {
  int root = h[1];
  swap(h[1], h[size]);
  swap(in1[h[1]], in1[h[size]]);
  size--;
  heapify(1);
  in1[root] = 0;
  return root;
}

void pop(int poz) {
  while(poz > 1 && dp[h[poz / 2]] > dp[h[poz]]) {
    swap(h[poz], h[poz / 2]);
    swap(in1[h[poz]], in1[h[poz / 2]]);
    poz /= 2;
  }
}

void insert(int x) {
  h[++size] = x;
  in1[x] = size;
  pop(size);
}

int main() {
  in >> n >> m;
  for(int i = 1; i <= m; i++) {
    in >> x >> y >> c;
    g[x].push_back({y, c});
    g[y].push_back({x, c});
  }
  dp[1] = 0;
  for(int i = 2; i <= n; i++)
    dp[i] = 1e9;
  solve(1);
  for(int i = 2; i <= n; i++)
    insert(i);
  for(int i = 1; i < n; i++) {
    int x = eraseRoot();
    solve(x);
    sol += dp[x];
    ans.push_back({x, tata[x]});
    for(auto j : g[x]) {
      if(in1[j.first])
        pop(in1[j.first]);
    }
  }
  out << sol << "\n" << n - 1 << "\n";
  for(auto i : ans)
    out << i.first << " " << i.second << "\n";
  return 0;
}