#include <cstdio>
#include <algorithm>

#define MAX 200050

using namespace std;

struct muchie
{
    int x, y, cost;
} v[MAX];

struct solutie
{
    int x, y;
} sol[MAX];

int n, m;
int tata[MAX];
int grad[MAX];
int cost;
int muchii;

bool cmpc(muchie a, muchie b)
{
    return a.cost < b.cost;
}

void citire()
{
    freopen("amp.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].cost);
        tata[i] = i;
        grad[i] = 1;
    }
    sort(v + 1, v + m + 1, cmpc);
    fclose(stdin);
}

void solve()
{
    int a, b;
    for(int i = 1; i <= m && muchii < n; i++)
    {
        a = v[i].x;
        b = v[i].y;
        while(a != tata[a])
        {
            a = tata[a];
        }
        while(b != tata[b])
        {
            b = tata[b];
        }
        if(a != b)
        {
            sol[++muchii].x = v[i].x;
            sol[muchii].y = v[i].y;
            cost += v[i].cost;
            if(grad[a] < grad[b])
                tata[a] = b;
            else if(grad[a] > grad[b])
                tata[b] = a;
            else
            {
                grad[a] += grad[b];
                tata[b] = a;
            }
        }
    }
}

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

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