#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 2e5 + 5;

struct muchie
{
    int x, y, cost;
}A;

vector <muchie> M;

vector <int> T(nmax), sol, rang(nmax);

int n, m, SOL, first, second;

bool cmp (muchie A, muchie B)
{
    return A.cost < B.cost;
}

void unite (int a, int b)
{
    if (rang[a] > rang[b]) T[b] = a;
    else
    {
        T[a] = b;
        if (rang[a] == rang[b]) rang[b]++;
    }
}

int findm (int a)
{
    if (T[a] != a) T[a] = findm(T[a]);
    return T[a];
}

void write ()
{
    fout << SOL << '\n' << n - 1 << '\n';
    for (int i=0; i<sol.size(); ++i)
    {
        fout << M[sol[i]].x << ' ' << M[sol[i]].y << '\n';
    }
}

int main()
{
    fin >> n >> m;
    assert(n >= 1 && n < nmax);
    assert(m >= 1 && m <= 4e5);
    for (int i=0; i<m; ++i)
    {
        fin >> A.x >> A.y >> A.cost;
        M.push_back(A);
        T[A.x] = A.x;
        T[A.y] = A.y;
    }
    sort(M.begin(), M.end(), cmp);
    for (int i=0; i<m; i++)
        if (T[M[i].x] != T[M[i].y])
        {
            first = findm(M[i].x);
            second = findm(M[i].y);
            if (first == second) continue;
            SOL = SOL + M[i].cost;
            unite(first, second);
            sol.push_back(i);
        }
    write();
    return 0;
}