#include <bits/stdc++.h>

using namespace std;

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

struct muchie
{
    int i, j, cost;
};

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

int n, m, t[200005];
muchie x[400005];

int find(int u)
{
    if (t[u] == u)
        return u;
    return t[u] = find(t[u]);
}

void unite(int u, int v)
{
    int rootU = find(u);
    int rootV = find(v);
    if (rootU != rootV)
    {
        t[rootV] = rootU;
    }
}

vector <pair<int, int>> rez;

int main()
{
    f >> n >> m;

    for (int i = 0; i < m; i++)
        f >> x[i].i >> x[i].j >> x[i].cost;

    sort(x, x + m, cmp);

    for (int i = 1; i <= n; i++)
        t[i] = i;

    int S = 0;
    for (int i = 0; i < m; i++)
    {
        if (find(x[i].i) != find(x[i].j))
        {
            S += x[i].cost;
            rez.push_back(make_pair(x[i].i, x[i].j));
            unite(x[i].i, x[i].j);
        }
    }

    g << S << '\n';
    g << n-1 << '\n';
    for(auto it:rez)
    {
        g << it.second << " " << it.first << '\n';
    }

    return 0;
}