#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define NMAX 200005
#define MAX 0x3f3f3f

using namespace std;

int n, m, tata[NMAX], deep[NMAX], distTotala;

vector <pair <int, int> > rezultat;
priority_queue <pair <int, pair<int, int> > > q;

void read()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; ++i)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        q.push(make_pair(-1*c, make_pair(x, y)));
    }
    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 solveKruskalAlgorithm()
{
    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();

        if(gasireTata(nod1) != gasireTata(nod2))
        {
            grupare(gasireTata(nod1), gasireTata(nod2));
            distTotala += cost;
            rezultat.push_back(make_pair(nod1, nod2));
            nAux--;
        }
    }
}

void afisare()
{
    printf("%d\n", distTotala);
    printf("%d\n", n-1);

    vector <pair <int, int> >::iterator it;
    for(it = rezultat.begin(); it!=rezultat.end(); ++it)
        printf("%d %d\n", it->first, it->second);
}

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