#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin ("apm.in");
ofstream cout ("apm.out");
#define NMAX 200005
struct Muchie
{
int u, v, cost;
bool operator <(const Muchie& other) const
{
return cost < other.cost;
}
};
int n, m, u, v, cost;
vector <Muchie> muchii;
vector <Muchie> rez;
int tata[NMAX];
void init()
{
for (int i = 1; i <= n; i++)
{
tata[i] = i;
}
}
int find(int n)
{
if (tata[n] == n) return n;
return tata[n] = find(tata[n]);
}
void unite(int a, int b)
{
int dad_a = find(a);
int dad_b = find(b);
if (dad_a != dad_b) tata[dad_a] = dad_b;
}
long long costt;
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++)
{
cin >> u >> v >> cost;
muchii.push_back({u, v, cost});
}
init();
sort(muchii.begin(), muchii.end());
for (int i = 0; i < m && rez.size() < n - 1; i++)
{
Muchie curent = muchii[i];
if (find(curent.u) != find(curent.v))
{
unite(curent.u, curent.v);
rez.push_back(curent);
costt += curent.cost;
}
}
cout << costt << '\n';
cout << rez.size() << '\n';
for (int i = 0; i < rez.size(); i++)
{
cout << rez[i].u << " " << rez[i].v << '\n';
}
return 0;
}