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

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

const int nmax=4e5+3;
int n,m,total,t[nmax],r[nmax],k;
pair<int,int>p[nmax];

struct muchie{
int x,y,c;
}v[nmax];

bool comp(muchie i,muchie j)
{
  return i.c<j.c;
}

void read(){
in>>n>>m;
for(int i=1;i<=m;i++)
 in>>v[i].x>>v[i].y>>v[i].c;

 for(int i=1;i<=m;i++)
{
  t[i]=i;
  r[i]=1;
}

 sort(v+1,v+m+1,comp);
}


int Find(int nod)
{
  while(t[nod]!=nod)
        nod=t[nod];
  return nod;
}

void unite(int x,int y)
{
 if(r[x]<r[y])
  t[x]=y;
  if(r[y]<r[x])
    t[y]=x;
  if(r[x]==r[y])
  {
     t[x]=y;
     r[y]++;
  }
}

void solve(){
for(int i=1;i<=m;i++)
{
  if(Find(v[i].x)!=Find(v[i].y))  {
    unite(Find(v[i].x),Find(v[i].y));
    p[++k].first=v[i].x;
    p[k].second=v[i].y;
    total=total+v[i].c;
  }
 }
 out<<total<<'\n';
 out<<n-1<<'\n';
 for(int i=1;i<=k;i++)
 {
   out<<p[i].second<<" "<<p[i].first<<'\n';

 }
}



int main(){
read();
solve();

return 0;
}