// af.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <algorithm>

using namespace std;

struct muchie
{
    long long a, b, c, d = 0; // c cost d da/nu
} x[4000], aux;

int main()
{
    long long i, j, n, m, total = 0, r[4000] = {}, nr = 0;

    cin >> n >> m;

    for (i = 0; i < m; i++)
    {
        cin >> x[i].a >> x[i].b >> x[i].c;
    }

    for (i = 0; i < m - 1; i++)
    {
        for (j = i + 1; j < m; j++)
        {
            if (x[i].c >= x[j].c)
            {
                aux = x[i];
                x[i] = x[j];
                x[j] = aux;
            }
        }
    }

    for (i = 1; i <= n; i++)
    {
        r[i] = i;
    }

    for (i = 0; i < m; i++)
    {
        if (r[x[i].a] != r[x[i].b])
        {
            total += x[i].c;

            x[i].d = 1;

            nr++;
        }

        for (j = 1; j <= n; j++)
        {
            if (r[j] == r[x[i].b])
            {
                r[j] = r[x[i].a];
            }
        }
    }

    cout << total << endl << nr << endl;

    for (i = 0; i < m; i++)
    {
        if (x[i].d == 1)
        {
            cout << x[i].a << " " << x[i].b << endl;
        }
    }
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file