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


const int nmax = 2e5 + 7;

int n, m;
bool vis[nmax];
vector<array<int, 2>> adj[nmax];

void solve() {
  
  cin >> n >> m;

  for (int i = 0; i < m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({w, v});
    adj[v].push_back({w, u});
  }

  priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq;
  
  vis[1] = true;
  for (auto e : adj[1]) pq.push({e[0], e[1], 1});

  int sum = 0;
  vector<array<int, 2>> ans;

  while (!pq.empty()) {
    auto [c, u, p] = pq.top(); pq.pop();
    if (vis[u]) continue;
    ans.push_back({p, u});
    vis[u] = true;
    sum += c;
    for (auto e : adj[u]) pq.push({e[0], e[1], u});
  }

  cout << sum << '\n';
  cout << n - 1 << '\n';
  for (auto [u, v] : ans) cout << u << ' ' << v << '\n';
}

int main() {

  #ifdef LOCAL
  freopen("file.in", "r", stdin);
  #else
  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);
  #endif

  ios_base::sync_with_stdio(false), cin.tie(NULL);

  solve();
}