#include <bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct muchie{
int x, y, cost;
};
int n, m, c;
vector<muchie> v;
vector<int> comp;
vector<muchie> apm;
bool cmp(muchie a, muchie b){
return a.cost<b.cost;
}
void kruskal(){
int x=0, y=0;
for(int i=0; i<m; i++){
x=comp[v[i].x];
y=comp[v[i].y];
if(x!=y){
apm.push_back(v[i]);
c+=v[i].cost;
for(int j=1; j<=n; j++){
if(comp[j]==y){
comp[j]=x;
}
}
}
if(apm.size()==n-1){
break;
}
}
}
int main()
{
in>>n>>m;
muchie M;
comp.resize(n+1);
for(int i=1; i<=n; i++){
comp[i]=i;
}
for(int i=1; i<=m; i++){
in>>M.x>>M.y>>M.cost;
v.push_back(M);
}
sort(v.begin(), v.end(), cmp);
kruskal();
out<<c<<'\n';
out<<apm.size()<<'\n';
for(auto el:apm){
out<<el.x<<" "<<el.y<<'\n';
}
return 0;
}