#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

typedef std::pair<int, std::pair<int, int>> PP;
typedef std::pair<int, int> P;

void read(std::vector<PP> &a, std::vector<P> &x)
{
    int n, m;
    std::ifstream fin("apm.in");
    fin >> m >> n;
    a.resize(n);
    x.resize(m + 1);
    for (int i = 0; i < n; i++)
    {
        fin >> a[i].second.first >> a[i].second.second >> a[i].first;
    }
    fin.close();
}

void MakeSet(std::vector<P> &x)
{
    for (int i = 1; i < x.size(); i++)
    {
        x[i].first = i;
        x[i].second = 1;
    }
}

int find(int t, std::vector<P> &x)
{
    if (x[t].first == t)
        return t;
    else
        x[t].first = find(x[t].first, x);
    return x[t].first;
}

int main()
{
    setbuf(stdin, NULL);
    setbuf(stdout, NULL);

    std::vector<PP> a;
    std::vector<P> x;
    std::vector<int> o;
    int sum = 0;
    read(a, x);
    MakeSet(x);

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

    int t1, t2;
    for (int i = 0; i < a.size(); i++)
    {
        t1 = find(a[i].second.first, x);
        t2 = find(a[i].second.second, x);
        if (t1 != t2)
        {
            o.push_back(i);
            sum += a[i].first;
            if (x[t1].second < x[t2].second)
            {
                x[t1].first = t2;
                x[t2].second = std::max(x[t2].second, x[t1].second + 1);
            }
            else
            {
                x[t2].first = t1;
                x[t1].second = std::max(x[t1].second, x[t2].second + 1);
            }
        }
    }

    std::ofstream fout("apm.out");
    fout << sum << "\n"
              << o.size() << "\n";
    for (int e : o)
    {
        fout << a[e].second.first << " " << a[e].second.second << "\n";
    }

    return 0;
}