#include <bits/stdc++.h>
#define t int
using namespace std;ifstream i("apm.in");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 n,m,x,y,c,s;main(){freopen("apm.in","w",stdout);i>>n>>m;iota(p,p+h,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;}printf("%d\n%d\n",s,n-1);for(auto e:f)printf("%d %d\n",e[0],e[1]);}