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

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

const int NMAX=200002;
struct date
{
  int  n2, c;
};
vector<date>G[NMAX];
int n, m;
int costMinim;
int d[NMAX], viz[NMAX];
vector<pair<int, int>>sol;

void Prim()
{
  int k, minim, dist, node=1;
  d[1] = 0;
  viz[1] = 1;
  for(int i=0;i<G[1].size();i++) {
    d[G[1][i].n2] = G[1][i].c;
  }
  for(int i=2;i<=n;i++)
    if(d[i]==0)
      d[i]=2e9;
  for (int pas = 2; pas <= n; pas++){
    minim = 2e9; k = 0;
    for (int i = 2; i <= n; i++)
      if (viz[i] == 0 && d[i] < minim){
        minim = d[i];
        k = i;
      }
    viz[k] = 1;
    costMinim += d[k];
    sol.push_back({node, k});
    for (int i=0;i<G[k].size();i++){
      dist=G[k][i].c;
      if (viz[G[k][i].n2]==0 && d[G[k][i].n2] > dist){
        d[G[k][i].n2] = dist;
      }
    }
    node=k;
  }
}


int main(){
  fin >> n >> m;
  for (int i = 1; i <= m; i++){
    int x, y, ct;
    fin >> x >> y >> ct;
    G[x].push_back({y, ct});
    G[y].push_back({x, ct});
  }
  Prim();
  fout << costMinim << "\n";
  fout<<sol.size()<<"\n";
  for(auto p : sol) {
    fout<<p.first<<" "<<p.second<<"\n";
  }

  return 0;
}