#include <bits/stdc++.h>
using namespace std;
ifstream i("apm.in");ofstream o("apm.out");
#define t int
t p[1<<18];
vector<vector<t>> g[2222];
set<vector<t>> 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+1111].push_back({x,y});}
for(c=0;c<2222;c++)for(auto e:g[c]){x=a(e[0]);y=a(e[1]);if(x^y){f.insert(e);s+=c-1111;}p[x]=y;}
o<<s<<"\n"<<n-1<<"\n";
for(auto e:f)o<<e[0]<<" "<<e[1]<<'\n';
}