#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int NMAX = 200000;
int n, m;
vector<pair<int, pair<int, int>>>graf;
vector<pair<int, int>>apm;
int rad[NMAX+1];
int radacina(int nod)
{
if (rad[nod] == nod)
return nod;
return rad[nod] = radacina(rad[nod]);
}
int cost_total;
int main()
{
in>>n>>m;
for (int i=1; i<=m; i++)
{
int cost, x, y;
in>>x>>y>>cost;
graf.push_back({cost, {x, y}});
rad[i] = i;///radacina pt fiecare este el insusi initial
}
sort(graf.begin(), graf.end());
/*
for (int i=0; i<m; i++)
{
out<<graf[i].second.first<<" "<<graf[i].second.second<<" "<<graf[i].first<<endl;
}*/
for (int i=0; i<m; i++)
{
int x = graf[i].second.first;
int y = graf[i].second.second;
int cost = graf[i].first;
if (radacina(x)!=radacina(y))
{
cost_total+=cost;
rad[radacina(x)] = radacina(y);
apm.push_back({x, y});
}
}
out<<cost_total<<"\n";
out<<n-1<<"\n";
for (int i=0; i<n-1; i++)
out<<apm[i].first<<" "<<apm[i].second<<"\n";
return 0;
}