#include  <fstream>
#include  <iostream>
#include  <vector>
#include  <algorithm>

using namespace std;

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

const int Nmax = 2e5 + 5;
int n, m, cnt;
vector<pair<int, int>>G[Nmax];
vector<int>G_min[Nmax];
int T[Nmax];
struct muchie{
  int x, y, c;
}V[Nmax];
struct cmp{
  bool operator()(muchie x, muchie y)
  {
    return x.c < y.c;
  }
};

void read()
{
  in>>n>>m;
  for(int i = 1; i <= m; i++)
  {
    in>>V[i].x>>V[i].y>>V[i].c;
    G[V[i].x].push_back({V[i].y, V[i].c});
    G[V[i].y].push_back({V[i].x, V[i].c});
  }
}

void unire(int x, int y)
{
  T[x] = y;
  //G_min[cnt].push_back(y);
}

int radacina(int nod)
{
  int r = nod;
  while(T[r] != r)
    r = T[r];
  while(T[nod] != nod)
  {
    unire(r, nod);
    nod = T[nod];
  }
  return nod;
}


void solve()
{
    int cost_min = 0;
    sort(V + 1, V + m + 1, cmp());
    for(int i = 1; i <= n; i++)
      T[i] = i;
    for(int i = 1; i <= m; i++)
    {
      int x = V[i].x,
          y = V[i].y,
          c = V[i].c;
      int X = radacina(x);
      int Y = radacina(y);
      if(X != Y)
        unire(X, Y), cost_min += c, cnt++, G_min[X].push_back(Y);
    }
  out<<cost_min<<'\n'<<cnt<<'\n';
  for(int i = 1; i <= cnt; i++, out<<'\n')
    for(auto it : G_min[i])
      out<<i<<' '<<it<<' ';
}

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