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

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

const int nmax=4e5+3;
int t[nmax],rg[nmax],n,m,k;

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

bool compare(edge a,edge b)
{
return a.c<b.c;
}

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

int radacina(int nod)
{
  while(nod!=t[nod])
        nod=t[nod];

  return nod;
}

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

pair<int,int>sol[nmax];
int sumaarb;

void solve(){
for(int i=1;i<=m;i++)
{
  if(radacina(v[i].x)!=radacina(v[i].y)){
        unite(radacina(v[i].x),radacina(v[i].y));
  sol[++k].first=v[i].y;
  sol[k].second=v[i].x;
  sumaarb+=v[i].c;
  }
 }
}


int main(){
read();
for(int i=1;i<=n;i++)
{
  t[i]=i;
  rg[i]=1;
}

solve();

out<<sumaarb<<'\n';
out<<n-1<<'\n';

for(int i=1;i<n;i++)
out<<sol[i].first<<" "<<sol[i].second<<'\n';


return 0;
}