#include <bits/stdc++.h>
using namespace std;
struct muchii {
 int x,y,cost;
 bool operator < (const muchii &a) const {
  return cost>a.cost;
 }
}var,var1;
int n,m,viz[200003],kontor,suma;vector <pair <int,int> > graf[200003];priority_queue <muchii> chestie;pair <int,int> sol[200003];
void prim () {
 while(!chestie.empty()) {
  var=chestie.top();
  if(viz[var.x]==1) {
   chestie.pop();
   continue;
  }
  viz[var.x]=1;chestie.pop();
  if(var.x!=var.y) {
   sol[++kontor]={var.x,var.y};
   suma+=var.cost;
  }
  for(int i=0;i<(int)graf[var.x].size();++i)
   if(viz[graf[var.x][i].first]==0) {
    var1.x=graf[var.x][i].first,var1.y=var.x,var1.cost=graf[var.x][i].second,chestie.push(var1);
   }
 }
}
int main () {
 int nr,nr1,nr2;
 freopen("apm.in","r",stdin);
 freopen("apm.out","w",stdout);
 scanf("%d%d", &n, &m);
 for(int i=1;i<=m;++i) {
  scanf("%d%d%d", &nr, &nr1, &nr2);
  graf[nr].push_back({nr1,nr2});graf[nr1].push_back({nr,nr2});
 }
 var.x=1;var.y=1;var.cost=0;
 chestie.push(var);prim();
 printf("%d\n%d\n", suma, kontor);
 for(int i=1;i<=kontor;++i)
  printf("%d %d\n", sol[i].first, sol[i].second);
 return 0;
}