#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct dsu
{
int tatici[200002], size[200002];
int find(int x)
{
if(tatici[x] != x)tatici[x] = find(tatici[x]);
return tatici[x];
}
void dsuUnion(int x, int y)
{
if(size[x] < size[y])
swap(x, y);
int f1 = find(x), f2 = find(y);
tatici[f2] = f1;
size[f1] += size[f2];
}
}a;
struct graf
{
int u, v, cost;
};
bool cmp(graf x, graf y)
{
return x.cost < y.cost;
};
int n, m, costMin, cntM;
vector<graf>edges;
vector<pair<int, int>>sol;
int main()
{
fin >> n >> m;
edges.resize(m);
for(int i = 1; i <= n; i++)
a.tatici[i] = i;
memset(a.size, 1, sizeof(a.size));
for(int i = 0; i < m; i++)
{
int x, y, c; fin >> x >> y >> c;
edges[i] = {x, y, c};
}
sort(edges.begin(), edges.end(), cmp);
for(auto i : edges)
{
int m1 = a.find(i.u);
int m2 = a.find(i.v);
if(m1 != m2 && cntM != n - 1)
{
cntM++;
costMin += i.cost;
a.dsuUnion(i.u, i.v);
sol.push_back({i.u, i.v});
}
}
fout << costMin << '\n' << n - 1 << '\n';
for(auto i : sol)
fout << i.first << " " << i.second << '\n';
return 0;
}