#include <bits/stdc++.h>

using namespace std;

using Edge = pair<int,int>;
using Graph = vector<vector<Edge>>;

int main(){
  ifstream cin("apm.in");
  ofstream cout("apm.out");

  ios_base::sync_with_stdio(false);

  int N, M;
  cin >> N >> M;

  Graph graph(N);

  for (int i = 0; i < M; i++){
    int u, v, w;
    cin >> u >> v >> w;
    u--; v--;

    graph[u].push_back({v, w});
    graph[v].push_back({u, w});
  }

  using Node = pair<int,int>;

  auto comp = [](Node L, Node R){
    return L.second > R.second;
  };

  priority_queue<Node, vector<Node>, decltype(comp)> heap(comp);
  vector<int> dist(N, numeric_limits<int>::max() / 2);
  vector<int> father(N, -1);
  vector<int> erased(N, 0);
  vector<tuple<int,int,int>> edges;

  dist[0] = 0;
  heap.push({0, 0});

  while (!heap.empty()){
    auto _node = heap.top();
    heap.pop();

    auto node = _node.first;
    auto d = _node.second;

    if (dist[node] != d)
      continue;

    erased[node] = 1;

    if (father[node] != -1){
      edges.push_back({node, father[node], dist[node]});
    }

    for (auto edge: graph[node]){
      auto v = edge.first;
      auto w = edge.second;

      if (dist[v] > w && !erased[v]){
        dist[v] = w;
        father[v] = node;
        heap.push({v, dist[v]});
      }
    }
  }

  cout << accumulate(edges.begin(), edges.end(), 0, [](int x, tuple<int,int,int> tpl){
    return x + get<2>(tpl);
  }) << "\n";

  cout << N - 1 << "\n";

  for (auto t: edges){
    int u, v;
    tie(u, v, std::ignore) = t;

    cout << u + 1 << " " << v + 1 << "\n";
  }

  return 0;
}