#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie
{
    int cost, x, y;

    bool operator<(const muchie &other) const
    {
        return cost < other.cost;
    }
};

int get_root(int node, vector<int> &t)
{
    if(t[node] == node)
        return node;
    return (t[node] = get_root(t[node], t));
}

void join(int x, int y, vector<int> &t, vector<int> &dim)
{
    x = get_root(x, t);
    y = get_root(y, t);
    if(dim[x] > dim[y])
        swap(x, y);
    t[x] = y;
    dim[y] += dim[x];
}

int main()
{
    int n, m;
    fin >> n >> m;

    vector<vector<pair<int, int>>> v(n + 1);
    vector<bool> vis(n + 1);
    vector<pair<int, int>> sol;
    vector<muchie> much;
    int sum = 0;
    vector<int> t(n + 1);
    vector<int> dim(n + 1, 1);

    for (int i = 1; i <= n; i++)
        t[i] = i;

    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        much.push_back(muchie{c, x, y});

        v[x].push_back(make_pair(y, c));
        v[y].push_back(make_pair(x, c));
    }

    sort(much.begin(), much.end());

    for (auto i: much)
    {
        if(get_root(i.x, t) != get_root(i.y, t))
        {
            join(i.x, i.y, t, dim);
            sol.emplace_back(i.x, i.y);
            sum += i.cost;
        }
    }

    fout << sum << "\n" << sol.size() << "\n";
    for(auto i : sol)
    {
        fout << i.first << " " << i.second << "\n";
    }


    return 0;
}