#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n, m;
int sef[200000];
vector<pair<int, pair<int, int>>> much;
vector<pair<int, int>> apm;

int sef_suprem(int nod)
{
    if (sef[nod] == nod)
        return nod;
    return sef[nod] = sef_suprem(sef[nod]);
}

void unire(int x, int y)
{
    int sefx = sef_suprem(x);
    int sefy = sef_suprem(y);
    if (sefx != sefy)
    {
        sef[sefx] = sefy;
    }
}
int main()
{
    int cost, n1, n2;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> n1 >> n2 >> cost;
        much.push_back({cost, {n1, n2}});
    }

    sort(much.begin(), much.end());

    for (int i = 1; i <= n; i++)
        sef[i] = i;
    int suma = 0;
    int muchii = 0;
    for (int i = 0; i < m && muchii < n - 1; i++)
    {
        int x = much[i].first;
        int y = much[i].second.first;
        int z = much[i].second.second;

        if (sef_suprem(y) != sef_suprem(z))
        {
            unire(y, z);
            suma += x;
            apm.push_back({y, z});
            muchii++;
        }
    }
    cout << suma << endl;
    cout << muchii << endl;
    for (int i = 0; i < apm.size(); i++)
        cout << apm[i].first << ' ' << apm[i].second << endl;
    return 0;
}