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

using namespace std;

const int NodMax = 200005;
const int MuchMax = 400005;

struct Muchie
{
    int m1, m2, c;

}v[MuchMax], rez[MuchMax];
int GR[NodMax], deep[NodMax];

int Find(int nod)
{
    if( GR[nod] !=nod )
        GR[nod] = Find(GR[nod]);

    else
        return nod;
}

void Join(int x, int y)
{
    if(deep[x] >= deep[y])
        GR[y] = x;

    else
        GR[x] = y;

    if(deep[x] == deep[y])
        ++deep[x];
}

int N, M;

void Read()
{
    scanf("%d %d", &N, &M);

    for(int i=1; i<=M; ++i)
    {
        scanf("%d %d %d", &v[i].m1, &v[i].m2, &v[i].c);
    }
}

bool cmp(Muchie a, Muchie b)
{
    return a.c < b.c;
}

void Kruskal()
{
    sort(v+1, v+M+1, cmp);

    int cost_total = 0;
    int edges = 0;

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

    for(int i=1; i<=M; ++i)
    {
        if(Find(v[i].m1) != Find(v[i].m2))
        {
            cost_total += v[i].c;
            Join(Find(v[i].m1),Find(v[i].m2));
            ++edges;
            rez[edges].m1 = v[i].m1;
            rez[edges].m2 = v[i].m2;
        }

        if(edges == N-1)
            break;
    }

    printf("%d\n%d\n", cost_total, edges);

    for(int i=1; i<=edges; ++i)
        printf("%d %d\n", rez[i].m1, rez[i].m2);
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    Read();
    Kruskal();
    return 0;
}