#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define PII pair<int,int>
#define Edge pair<int,PII>
#define cost first
#define x second.first
#define y second.second

ifstream is ("apm.in");
ofstream os ("apm.out");

int N, M, T[200002], R[200002], APMcost;
vector <Edge> E;
vector <PII> APM;

void Kruskal();

int Root(int k);
void Unite(int a, int b);

int main()
{
    is >> N >> M;
    for (int i = 1, a, b, c; i <= M; ++i)
    {
        is >> a >> b >> c;
        E.push_back({c, {a, b}});
    }
    Kruskal();
    is.close();
    is.close();
}

void Kruskal()
{
    for (int i = 1; i <= N; ++i)
        T[i] = i, R[i] = 1;
    sort(E.begin(), E.end());
    int Rx, Ry;
    for (const auto& m : E)
    {
        Rx = Root(m.x);
        Ry = Root(m.y);
        if (Rx == Ry);
        else
        {
            Unite(Rx, Ry);
            APMcost += m.cost;
            APM.push_back({m.x, m.y});
        }
    }
    os << APMcost << '\n' << N-1 << '\n';
    for (const auto& m : APM)
        os << m.first << ' ' << m.second << '\n';
};

int Root(int k)
{
    int r = k;
    for (; T[r] != r; r = T[r]);
    for (int s; T[k] != k; s = T[k], T[k] = r, k = s);
    return r;
};

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