#include <bits/stdc++.h>

using namespace std;

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

bool SortParam(const pair<pair<int, int>, int> &x, const pair<pair<int, int>, int> &y)
{
  return (x.second < y.second);
}

class Graf
{
private:
  int N, M;
  vector<pair<pair<int, int>, int>> adj;
  vector<pair<int, int>> sol;
  vector<int> parinte;
  vector<int> rank;

public:
  Graf(int);
  void adaugaMuchie(int, int, int);
  void Kruskall();
  void Leaga(int, int);
  int Gaseste(int);
};

Graf ::Graf(int n)
{
  N = n;
  parinte.resize(N + 1);
  rank.resize(N + 1);
}
void Graf ::adaugaMuchie(int x, int y, int w)
{
  adj.push_back(make_pair(make_pair(x, y), w));
}

int Graf ::Gaseste(int x)
{
  if (x == parinte[x])
    return x;
  return Gaseste(parinte[x]);
}

void Graf::Leaga(int a, int b)
{
  int x = Gaseste(a);
  int y = Gaseste(b);

  if (rank[x] >= rank[y])
  {
    parinte[y] = x;
    M++;
  }
  else if (rank[x] < rank[y])
  {
    parinte[x] = y;
    M++;
  }
  else
  {
    parinte[x] = y;
    rank[y] += 1;
  }
}
void Graf ::Kruskall()
{
  int cost = 0, i, x, y;
  M = 0;

  for (i = 1; i <= N; i++)
  {
    parinte[i] = i;
    rank[i] = 1;
  }
  sort(adj.begin(), adj.end(), SortParam);
  for (i = 0; i < adj.size(); i++)
  {
    x = Gaseste(adj[i].first.first);
    y = Gaseste(adj[i].first.second);
    if (x != y)
    {
      sol.push_back(make_pair(x, y));
      Leaga(y, x);
      cost += adj[i].second;
    }
  }
  fout << cost << '\n';
  fout << M << '\n';
  for (i = 0; i < M; i++)
    fout << sol[i].first << ' ' << sol[i].second << '\n';
  for (i = 0; i < N; i++)
    fout << rank[i] << " ";
}

int main()
{
  int n, m, i, x, y, w;
  fin >> n >> m;
  Graf G(n);
  for (i = 1; i <= m; i++)
  {
    fin >> x >> y >> w;
    G.adaugaMuchie(x, y, w);
  }
  G.Kruskall();
  return 0;
}