// APM - cu disjoint sets
#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
const int Nmax = 222222;

int d[Nmax];
int rnk[Nmax];

int root(int x)
{
    if (x != d[x])
        d[x] = root(d[x]);
    return d[x];
}

bool join(int x, int y)
{
    x = root(x), y = root(y);
    if (x != y)
    {
        if (rnk[x] < rnk[y])
            d[x] = y;
        else
        {
            d[y] = x;
            if (rnk[x] == rnk[y])
                rnk[x]++;
        }
        return 1;
    }
    return 0;
}

int main()
{
    ifstream f ("apm.in");
    ofstream g ("apm.out");

    int N, M, a, b, weight;
    f >> N >> M;
    for (int i = 1; i <= N; i++)
        d[i] = i;

    vector<pair<int, pair<int, int>>> G(M);

    while(M--)
    {
        f >> a >> b >> weight;
        G[M] = make_pair(weight, make_pair(a, b));
    }
    sort(G.begin(), G.end());

    int cost = 0;
    int cnt = 0;
    vector<pair<int, int>> solution;

    for (auto edge: G)
        if (join(edge.second.first, edge.second.second))
        {
            cost += edge.first;
            cnt++;
            solution.push_back(edge.second);
            if (cnt == N-1) break;
        }

    g << cost << '\n';
    g << solution.size() << '\n';
    for (auto edge: solution)
        g << edge.first << ' ' << edge.second << '\n';
    

    return 0;
}