//APM - Kruskal
#include <fstream>
#include <algorithm>
#include <bitset>
using namespace std;
typedef struct muchie{
        int x,y,cost;
        };
const int NMAX=200002,MMAX=400004;
ifstream fin("apm.in");
ofstream fout("apm.out");
int N,M,t[NMAX],nr[NMAX],sol;
muchie a[MMAX],v[NMAX];
bitset<NMAX> u;
int cmp(muchie A,muchie B){
    return A.cost<B.cost;
    }
int find(int x){
    int rad,y=x,z;
    while (t[y]!=y) y=t[y];
    rad=y;y=x;
    while (y!=rad){
         z=t[y];;
         t[y]=rad;
         y=z;}
    return rad;
    } 
void unite(int x,int y){
     if (nr[x]<nr[y])
      {
       t[x]=y;
       nr[y]+=nr[x];
      }
      else
      {
       t[y]=x;
       nr[y]+=nr[x];
      }
     }
int main(){
    int i,p;
    fin>>N>>M;
    for (i=0;i<M;++i)
      fin>>a[i].x>>a[i].y>>a[i].cost;
    sort(a,a+M,cmp);
    for (i=1;i<=N;++i) t[i]=i,nr[i]=1;
    p=0;
    for (i=1;i<N;++i){
        while (p<M && find(a[p].x)==find(a[p].y)) ++p;
        sol+=a[p].cost;
        unite(find(a[p].x),find(a[p].y));
        v[i]=a[p];
        }
    fout<<sol<<'\n';
    fout<<N-1<<'\n';
    for (i=1;i<N;++i)
      fout<<v[i].x<<' '<<v[i].y<<'\n';
    return 0;
}