#include <bits/stdc++.h>
using namespace std;
ifstream i("apm.in");ofstream o("apm.out");
#define t int
const t h=3e5;
t p[h];
vector<vector<t>> g[h+h],f;
t a(t x) {if(x^p[x])p[x]=a(p[x]);return p[x];}
t main() {
t n,m,x,y,c,s=0;i>>n>>m;
iota(p,p+n+1,0);
while(m--){i>>x>>y>>c;g[c+h].push_back({x,y});}
for(c=0;c<h+h;c++)for(auto e:g[c]){x=a(e[0]);y=a(e[1]);if(x^y){f.push_back(e);s+=c-h;}p[x]=y;}
o<<s<<"\n"<<n-1<<"\n";
for(auto e:f)o<<e[0]<<" "<<e[1]<<'\n';
}