#include <bits/stdc++.h>

using namespace std;

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

const int mmax = 400000, nmax = 200000;

int n, m, p[nmax + 5], r[nmax + 5];
long long ans = 0;
vector <pair <int, int> > sol;

struct Muchie
{
    int x, y, cost;
}v[mmax + 5];

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

int Find(int x)
{
    int aux = x;
    while (p[aux] != aux) aux = p[aux];
    while (p[x] != x)
    {
        int ne = p[x];
        p[x] = aux, x = ne;
    }
    return aux;
}

void Union(int x, int y)
{
    int p1 = Find(x);
    int p2 = Find(y);
    if (r[p1] == r[p2])
    {
        p[p2] = p1;
        r[p1]++;
    }
    else if (r[p1] > r[p2])
    {
        p[p2] = p1;
    }
    else
    {
        p[p1] = p2;
    }

}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; ++i) p[i] = i;
    for (int i = 1; i <= m; ++i)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        v[i] = {x, y, cost};
    }
    sort(v + 1, v + m + 1, cmp);
    for (int i = 1; i <= m; ++i)
        if (Find(v[i].x) != Find(v[i].y))
            Union(v[i].x, v[i].y), ans = ans + v[i].cost, sol.push_back({v[i].x, v[i].y});
    fout << ans << "\n";
    fout << n - 1 << "\n";
    for (int i = 1; i < n; ++i)
        fout << sol[i - 1].first << " " << sol[i - 1].second << "\n";
    fin.close();
    fout.close();
    return 0;
}