#include <bits/stdc++.h>

using namespace std;

typedef pair<int, pair<int, int>> ppi;

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

vector<int> RR, TT;
vector<ppi> edges, answ;

class Comparator
{
public:
    bool operator()(const ppi &a, const ppi &b){
        return a.second.second < b.second.second;
    }
};

int FindT(int x)
{
    int aux = x;

    for (;TT[aux] != aux; aux = TT[aux]);

    int c;
    for (;TT[x] != x; c = x, x = TT[x], TT[c] = aux);

    return aux;
}

void Union(int x, int y)
{
    if (RR[x] >= RR[y])
        TT[y] = x;
    else
        TT[x] = y;

    if (RR[x] == RR[y])
        ++RR[x];
}

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

    RR.resize(n + 1);
    TT.resize(n + 1);

    for (int i = 1; i <= n; ++i)
    {
        TT[i] = i;
        RR[i] = 1;
    }

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

    sort(edges.begin(), edges.end(), Comparator());

    int cost = 0;
    int ind = 0;
    int to_add = n - 1;

    while (to_add)
    {
        int x = edges[ind].first;
        int y = edges[ind].second.first;
        int c = edges[ind].second.second;

        if ( (x = FindT(x)) != (y = FindT(y)))
        {
            cost += c;
            Union(x, y);
            --to_add;
            answ.push_back(edges[ind]);
        }
        ++ind;
    }

    fout << cost << "\n" << n - 1 << "\n";
    for_each(answ.begin(), answ.end(), [](const ppi& e){fout << e.first << " " << e.second.first << "\n";});

    return 0;
}