#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");


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);
}