#include <bits/stdc++.h>

using namespace std;

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

int M, N, sol, root[200003], s[200003];

struct art
{
    int x, y, cost;
} E[400003];

struct cmp
{
    bool operator () (const art &a, const art &b)
    {
        return a.cost < b.cost;
    }
};

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

void Unite (int x, int y)
{
    x = GetRoot(x);
    y = GetRoot(y);
    if (x != y)
    {
       root[x] = y;
    }
}

int main ()
{
    fin >> N >> M;
    for (int i = 1; i <= M; ++ i)
    {
        fin >> E[i].x >> E[i].y >> E[i].cost;
    }
    sort (E+1, E+M+1, cmp());
    for (int i = 1; i <= N; ++ i)
    {
        root[i] = i;
    }

    for (int i = 1; i <= M; ++ i)
    {
        if (GetRoot(E[i].x) != GetRoot (E[i].y))
        {
            sol += E[i].cost;
            Unite (E[i].x, E[i].y);
            s[++s[0]] = i;
        }
    }

    fout << sol << '\n' << N-1  << '\n';
    for (int i = 1; i < N; ++ i)
    {
        fout << E[s[i]].x << ' ' << E[s[i]].y << '\n';
    }

    fout.close();
    return 0;
}