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

using namespace std;

int cmp(const void *p1, const void * p2)
{
    int *a = *(int**)p1;
    int *b = *(int**)p2;

    return (a[2] - b[2]);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out", "w", stdout);
    int **elek, n, m, ertek;

    cin >> n >> m;
    elek = new int* [m];

    for (int i = 0 ; i < m ; i++)
    {
        elek[i] = new int [3];
        cin >> elek[i][0] >> elek[i][1] >> elek[i][2];
    }

    qsort(elek ,m, sizeof(int*), cmp);

    int halm[n+1];

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

    int k = n-1, el = 0,s=0;

    while (k)
    {
        int x = elek[el][0];
        int y = elek[el][1];

        if (halm[x] != halm[y])
        {
            cout << x << " " << y << "\n";
            for (int i = 1 ; i <= n ; i++)
            {
                if (halm[i] == halm[x])
                    halm[i] = halm[y];
            }

            s += elek[el][2];
            k--;
        }
        el++;
    }

    cout << s << "\n";

    for(int i = 0; i < m; i++){
        delete [] elek[i];
    }
    delete [] elek;

    return 0;
}