#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define NMAX 200005

using namespace std;

int N, M, tata[NMAX], deep[NMAX], distTotala;
vector <pair <int, int> > sol;
priority_queue <pair < int, pair <int, int> > > Q;

void read()
{
    scanf("%d %d", &N, &M);
    for(int i=1; i<=M; ++i)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        Q.push(make_pair(-1*c, make_pair(a, b)));
    }
    for(int i=1; i<=N; ++i)
        tata[i] = i;
}

int gasireTata(int nod)
{
    while(nod != tata[nod])
        nod = tata[nod];
    return nod;
}

void grupare(int x, int y)
{
    if(deep[x] > deep[y])
        tata[y] = x;
    else if(deep[x] < deep[y])
        tata[x] = y;
    else
    {
        tata[y] = x;
        deep[x]++;
    }
}

void apmKruskal()
{
    int NAux = N - 1;
    while(NAux && !Q.empty())
    {
        int cost = -1 * Q.top().first;
        int nod1 = Q.top().second.first;
        int nod2 = Q.top().second.second;
        Q.pop();
        int t1 = gasireTata(nod1);
        int t2 = gasireTata(nod2);
        if(t1 != t2)
        {
            grupare(t1, t2);
            distTotala += cost;
            sol.push_back(make_pair(nod1, nod2));
            NAux--;
        }
    }
}

void print()
{
    printf("%d\n", distTotala);
    printf("%d\n", N-1);
    vector <pair <int, int> >::iterator it;
    for(it = sol.begin(); it != sol.end(); ++it)
        printf("%d %d\n", it->first, it->second);
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    read();
    apmKruskal();
    print();
    return 0;
}