#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<double, double>;
using pld = pair<ld, ld>;
vector<pair<int, pi>> adj;
vector<int> parent, tree_depth;
ifstream fin("apm.in");
ofstream fout("apm.out");
inline int find_root(const int vertex)
{
if (parent[vertex] == vertex)
{
return vertex;
}
return parent[vertex] = find_root(parent[vertex]);
}
void merge(int vertex1, int vertex2)
{
vertex1 = find_root(vertex1), vertex2 = find_root(vertex2);
if (vertex1 != vertex2)
{
if (tree_depth[vertex1] < tree_depth[vertex2])
{
swap(vertex1, vertex2);
}
parent[vertex2] = vertex1;
tree_depth[vertex1] += tree_depth[vertex1] == tree_depth[vertex2];
}
}
void Kruskal(const int nr_nodes)
{
parent.resize(nr_nodes + 1), tree_depth.resize(nr_nodes + 1);
iota(begin(parent), end(parent), 0);
sort(begin(adj), end(adj));
int min_mst_cost{};
vector<pi> mst;
for (const auto &edge : adj)
{
const int weight = edge.first, node1 = edge.second.first, node2 = edge.second.second;
if (find_root(node1) != find_root(node2))
{
merge(node1, node2);
min_mst_cost += weight;
mst.push_back({node1, node2});
}
}
fout << min_mst_cost << "\n" << mst.size() << "\n";
for (const auto &mst_edge : mst)
{
fout << mst_edge.first << " " << mst_edge.second << "\n";
}
}
int main()
{
int N, M;
fin >> N >> M;
while (M--)
{
int x, y, weight;
fin >> x >> y >> weight;
// adj.push_back({weight, {x, y}});
adj.push_back({weight, {y, x}});
}
Kruskal(N);
}