#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<int> parent, tree_depth;


inline int find_root(const int vertex)
{
    if (parent[vertex] == vertex)
    {
        return vertex;
    }
    return parent[vertex] = find_root(parent[vertex]);
}


void merge(int node1, int node2)
{
    node1 = find_root(node1), node2 = find_root(node2);
    if (tree_depth[node1] < tree_depth[node2])
    {
        swap(node1, node2);
    }
    tree_depth[node1] += tree_depth[node1] == tree_depth[node2];
    parent[node2] = node1;
}


int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");

    int N, M;
    cin >> N >> M;

    vector<pair<int, pi>> adj;
    while (M--)
    {
        int X, Y, C;
        cin >> X >> Y >> C;

        adj.push_back({C, {X, Y}});
        adj.push_back({C, {Y, X}});
    }

    vector<pi> mst_edges;
    int res_min_cost{};

    auto Kruskal = [&]() -> void
    {
        parent.resize(N + 1), tree_depth.resize(N + 1);
        iota(begin(parent), end(parent), 0);
        sort(begin(adj), end(adj));

        for (const auto &edge : adj)
        {
            const int cost = edge.first, node1 = edge.second.first, node2 = edge.second.second;

            if (find_root(node1) != find_root(node2))
            {
                merge(node1, node2);
                res_min_cost += cost;
                mst_edges.emplace_back(node1, node2);
            }
        }
    };

    Kruskal();
    cout << res_min_cost << "\n" << N - 1 << "\n";
    for (const auto &apm_edge : mst_edges)
    {
        cout << apm_edge.first << " " << apm_edge.second << "\n";
    }
}