#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int maxn = 400001;
int n,m,x[maxn],y[maxn],c[maxn],ind[maxn],grup[maxn],indice[maxn];
int sum;
vector <int> sol;
bool cmp(const int& x,const int& y)
{
return c[x] < c[y];
}
int grupa(int x)
{
if(grup[x] == x) return x;
grup[x] = grupa(grup[x]);
return grup[x];
}
void reuniune(int x, int y)
{
grup[grupa(x)] = grupa(y);
}
int main()
{
f >> n >> m;
for(int i = 1; i <= m; ++i)
{
f >> x[i] >> y[i] >> c[i];
indice[i] = i;
}
for(int i = 1; i <= n; ++i) grup[i] = i;
sort(indice + 1, indice + m + 1, cmp);
for(int i = 1; i <= m; i++)
if(grupa(x[indice[i]]) != grupa(y[indice[i]]))
{
sum += c[indice[i]];
reuniune(x[indice[i]],y[indice[i]]);
sol.push_back(indice[i]);
}
g << sum << "\n" << n - 1 << "\n";
for(vector<int>::iterator it = sol.begin(); it != sol.end(); ++it)
g << x[*it] << " " << y[*it] << "\n";
return 0;
}