#include <cstdio>
#include <algorithm>

#define maxim 200050

using namespace std;

struct lat
{
    int x, y, costul;
} v[maxim];

struct solutieutie
{
    int x, y;
} solutie[maxim];

int n, m, t[maxim], g[maxim], costul, mu;

bool comprc(lat a, lat b)
{
    return a.costul < b.costul;
}

void citire()
{
    freopen("apm.in", "r", stdin);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &v[i].x, &v[i].y, &v[i].costul);
        t[i] = i;
        g[i] = 1;
    }
    sort(v + 1, v + m + 1, comprc);
    fclose(stdin);
}

void rezolv()
{
    int a, b;
    for(int i = 1; i <= m && mu < n; i++)
    {
        a = v[i].x;
        b = v[i].y;
        while(a != t[a])
        {
            a = t[a];
        }
        while(b != t[b])
        {
            b = t[b];
        }
        if(a != b)
        {
            solutie[++mu].x = v[i].x;
            solutie[mu].y = v[i].y;
            costul += v[i].costul;

            if(g[a] < g[b])
                t[a] = b;
            else if(g[a] > g[b])
                t[b] = a;
            else
            {
                g[a] += g[b];
                t[b] = a;
            }
        }
    }
}

void afisare()
{
    freopen("apm.out", "w", stdout);
    printf("%d\n%d\n", costul, n - 1);
    for(int i = 1; i < n; i++)
    {
        printf("%d %d\n", solutie[i].x, solutie[i].y);
    }
}

int main()
{
    citire();
    rezolv();
    afisare();
    return 0;
}