#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, c, t[200001], k, rg[200001];

struct Muchie
{
    int x, y, cost;
}v[400001], rez[200000];

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

void input()
{
    fin >> n >> m;
    for(int i = 1; i <= m; ++i)
        fin >> v[i].x >> v[i].y >> v[i].cost;
    sort(v + 1, v + m + 1, Compare);
    for(int i = 1; i <= n; ++i)
        t[i] = -1, rg[i] = 1;
}

int find(int i)
{
    if (t[i] == -1)
        return i;

    return t[i] = find(t[i]);
}

void unite(int x, int y)
{
    int s1 = find(x);
    int s2 = find(y);
    if (s1 != s2)
    {
        if (rg[s1] < rg[s2])
        {
            t[s1] = s2;
            rg[s2] += rg[s1];
        }
        else
        {
            t[s2] = s1;
            rg[s1] += rg[s2];
        }
    }
}

void Solve()
{
    /**bad time comlexity
    int k = 0, i = 1;
    while(k < n - 1)
    {
        int x = v[i].x, y = v[i].y;
        if(t[x] != t[y])
        {
            c += v[i].cost;
            rez[++ind].x = y, rez[ind].y = x;
            int tx = t[x], ty = t[y];
            for(int j = 1; j <= n; ++j)
                if(t[j] == ty)
                    t[j] = tx;
            k++;
        }
        i++;
    }*/
    int i;
    for(i = 1, k = 0; i <= m && k < n - 1; ++i)
    {
        int x = find(v[i].x), y = find(v[i].y);
        if(x != y)
        {
            c += v[i].cost;
            rez[++k].x = v[i].x;
            rez[k].y = v[i].y;
            unite(v[i].x, v[i].y);
        }
    }
}

void output()
{
    fout << c << '\n' << n - 1 << '\n';
    for(int i = 1; i <= k; ++i)
        fout << rez[i].x << ' ' << rez[i].y << '\n';
}

int main()
{
    input();
    Solve();
    output();
    return 0;
}