#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define NMAX 200001
#define MMAX 400001

using namespace std;

int X, Y, C, N, M, l=1;
int costMinim;
int tata[NMAX];
int sol[MMAX];
int ad[NMAX];

struct pereche
{
    int v1;
    int v2;
    int cost;
    pereche(int a=0, int b=0, int c=0)
    {
        v1 = a;
        v2 = b;
        cost = c;
    }

}vec[MMAX];

int radacina(int x)
{
    int aux = x, tmp = x;
    while (tata[aux] != aux)
        aux = tata[aux];
    while(tata[tmp] != tmp)
    {
        x = tata[tmp];
        tata[tmp] = aux;
        tmp = x;
    }

    return aux;
}

bool comparator(pereche a, pereche b)
{
    return a.cost < b.cost;
}

void unire(int x, int y)
{
    if(ad[x] == ad[y])
    {
        tata[x] = y;
        ad[y]++;
        return;
    }

    if(ad[x] < ad[y])
    {
        tata[x] = y;
    }
    else
    {
        tata[y] = x;
    }
}

void solve()
{
    for (int i=1; i<=M; i++)
    {
        if (radacina(vec[i].v1) != radacina(vec[i].v2))
        {
            costMinim+=vec[i].cost;
            unire(radacina(vec[i].v1), radacina(vec[i].v2));
            sol[l++] = i;
        }
    }
}
void read()
{
    scanf("%d %d\n", &N, &M);
    for (int i=1; i<=M; i++)
    {
        scanf("%d %d %d\n", &vec[i].v1, &vec[i].v2, &vec[i].cost);
    }

    for (int i=1; i<=N; i++)
        tata[i] = i;
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    read();
    sort(vec+1, vec+M+1, comparator);
    solve();
    printf("%d\n%d\n", costMinim, N-1);
    for (int i=1; i<N; i++)
        printf("%d %d\n", vec[sol[i]].v1, vec[sol[i]].v2);
    return 0;
}