#include <iostream>
#include <fstream>
#include <algorithm>
#define mod 10000
#define x first
#define y second
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int t[100001],n,m,i,tip,rx,ry,x,y,j,cost;
pair <int,int> sol[200001];
int k;
pair <int ,pair<int,int>>a[400001];
int rad(int x){
while(t[x]>0){
    x=t[x];
}
return x;

}
int main()
{
  fin>>n>>m;
  for(i=1;i<=n;i++)
    t[i]=-1;
for(j=1;j<=m;j++){
    fin>>a[j].y.x>>a[j].y.y>>a[j].x;
}
sort(a+1,a+m+1);
for(j=1;j<=m;j++){
    rx=rad(a[j].y.x);
    ry=rad(a[j].y.y);
    if(rx==ry){
       continue;
    }
  else{
    cost+=a[j].x;
    sol[++k].x=a[j].y.x;
    sol[k].y=a[j].y.y;
    if(t[rx]<t[ry]){
        t[ry]=rx;

    }
    else
        t[rx]=ry;
  }
}
fout<<cost<<"\n"<<k<<"\n";
for(i=1;i<=k;i++)
    fout<<sol[i].x<<" "<<sol[i].y<<"\n";
}