#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n, m;
int parent[200001], ranking[200001];

struct edge{
  int node1, node2, cost;
};

vector<edge> edges;
vector<pair<int, int>> result;
int total_cost;

bool cmp(edge e1, edge e2)
{
  return e1.cost < e2.cost;
}

void read()
{
  f>>n>>m;
  int x, y, z;
  for(int i = 1;i <= m;++i)
    f>>x>>y>>z, edges.push_back({x, y, z});
}

int find(int node)
{
  if(parent[node] == node)
    return node;

  return parent[node] = find(parent[node]);
}

void unite(int node1, int node2)
{
  if(ranking[node1] > ranking[node2])
    parent[node2] = node1, ranking[node1] += ranking[node2];
  else
    parent[node1] = node2, ranking[node2] += ranking[node1];
}


void solve()
{
  sort(edges.begin(), edges.end(), cmp);
  
  for(int i = 1;i <= n;++i)
    parent[i] = i, ranking[i] = 1;

  for(auto it : edges)
    if(find(it.node1) != find(it.node2))
      {
        total_cost += it.cost;
        unite(find(it.node1), find(it.node2));
        result.push_back(make_pair(it.node1, it.node2));
      }

  g<<total_cost<<'\n'<<n - 1<<'\n';
  for(auto it : result)
    g<<it.first<<" "<<it.second<<'\n';
}

int main()
{
  read();
  solve();
  return 0;
}