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

#define INF 200000000

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

using namespace std;

int dist[200000];
bool vis[200000];

int n, m;

vector <pair<int, int> > ponderi[200000];

priority_queue< pair<int, int>, vector <pair<int, int> >, greater <pair<int, int> > > Q;

int t[200000];

int main () {

  //initializare
  fin >> n >> m;
  int start = 0;
  for(int i = 1;i<=m;i++){
    int x, y ,z;
    fin >> x >> y >> z;
    x--;
    y--;
    ponderi[x].push_back({y,z});
    ponderi[y].push_back({x,z});
  }
  for (int i = 0; i < n; ++i) {
    dist[i]  = INF;
    vis[i] = false;
  }

  dist[start] = 0;
  t[start] = -1;
  Q.push({0, start});

  int solutie = 0;

// https://www.infoarena.ro/problema/apm

  while(!Q.empty()) {
    pair<int, int> top = Q.top();
    Q.pop();
    int node = top.second;

    if (vis[node] == true)
      continue;

    vis[node] = true;
    solutie += dist[node];
    // parcurgem vecinii pentru a actualiza dist

    /*
     vis[nod]=1;
      for(int i=0;i<pondere[nod].size();i++){
        if(pondere[nod][i].second+dist[nod]<dist[pondere[nod][i].first]){
          q.push({-pondere[nod][i].second+dist[nod],pondere[nod[i]].first});
          dist[pondere[nod][i].first]=pondere[nod][i].second+dist[nod];
        }
      }
    */



    for (int i = 0; i < ponderi[node].size(); ++i) {
      int cost = ponderi[node][i].second;
      int vecin = ponderi[node][i].first;

      if (vis[vecin] == false && dist[vecin] > cost) {
        // adaugam muchie de la nod-vecin
        // nod2 - vecin

        Q.push({cost, vecin});
        dist[vecin] = cost;
        t[vecin] = node;
      }
    }
  }

  fout << solutie << "\n" << n - 1 << "\n";

  for (int i = 0; i < n; ++i) {
    if (t[i] >= 0) {
      fout << t[i] + 1 << " " << i + 1<< "\n";
    }
  }

  return 0;

}