#include <fstream>
#include <vector>
#include <functional>
#include <bits/stdc++.h>
#define nmax 400005
#define nmax1 200005

using namespace std;

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

inline int find(int x,int parent[]){
  if(parent[x]==x)
  	return parent[x];
   parent[x]=find(parent[x],parent);
   return parent[x]; 
}
void unite(int x,int y,int parent[]){
  parent[find(y,parent)]=find(x,parent);
}

struct muchie{
  int x;
  int y;
  int cost;
  bool operator<(muchie b){
    return this->cost<b.cost;
  }
};

int main(){
   int n, m, x, y, cost, i;
   	ios::sync_with_stdio(false);
    f>>n>>m;
    muchie edge[nmax];
    int parent[nmax1]={0};
    int indice[nmax1]={0};
    for(i=1;i<=m;++i){
    	f>>edge[i].x>>edge[i].y>>edge[i].cost;
    }
    sort(edge+1,edge+m+1);
    for(i=1;i<=n;i++)
       	parent[i]=i;
     int k=0, sol=0;
    for(i=1;i<=m && k<=n-1;i++){
          if(find(edge[i].x,parent)!=find(edge[i].y,parent)){
          		unite(edge[i].x,edge[i].y,parent);
          		sol+=edge[i].cost;
          		k++;
          		indice[k]=i;
          }
          
    }
    g<<sol<<"\n";
    g<<n-1<<"\n";
    for(i=1;i<=(n-1);i++)
    	g<<edge[indice[i]].y<<" "<<edge[indice[i]].x<<" "<<"\n";
      
}