#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int N = 200000 + 7;
int piz;
int hardcore;

struct itz
{
    int x;
    int c;
};

vector<itz> g[N];
int t[N];

int jeg(int pou)
{
    if (t[pou] == pou)
    {
        return pou;
    }
    else
    {
        return t[pou] = jeg(t[pou]);
    }
}

void sex(int plm, int j)
{
    plm = jeg(plm);
    j = jeg(j);
    t[plm] = j;
}

int main()
{
    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout);

    cin >> piz >> hardcore;
    vector<pair<int, int>> oinc;
    for (int plm = 1; plm <= piz; plm++)
    {
        t[plm] = plm;
    }
    for (int plm = 1; plm <= hardcore; plm++)
    {
        int pou, b, c;
        cin >> pou >> b >> c;
        g[pou].push_back({b, c});
        g[b].push_back({pou, c});
    }
    int porc = 0;
    while (1)
    {
        int cnt = 0;
        for (int plm = 1; plm <= piz; plm++)
        {
            int minc = (1 << 30), node;
            for (auto &it : g[plm])
            {
                int j = it.x;
                int c = it.c;
                if (jeg(j) != jeg(plm) && minc > c)
                {
                    minc = c;
                    node = j;
                }
            }
            if (minc != (1 << 30))
            {
                sex(plm, node);
                oinc.push_back({plm, node});
                porc += minc;
            }
        }
        for (int plm = 1; plm <= piz; plm++)
        {
            cnt += (t[plm] == plm);
        }
        if (cnt == 1)
        {
            break;
        }
    }
    cout << porc << "\n";
    cout << piz - 1 << "\n";
    for (auto &it : oinc)
    {
        cout << it.first << " " << it.second << "\n";
    }
}