#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

FILE *in = fopen("apm.in","r");
FILE *out = fopen("apm.out","w");

int n,m,rad[200001];
vector < pair<int,int> > q;

struct matr
{
    int lin,col,cost;
} v[200001*2];

void citire()
{
    int i;
    fscanf(in, "%d %d", &n, &m);
    for(i=1; i<=m; i++)
    {
        fscanf(in, "%d %d %d", &v[i].lin, &v[i].col, &v[i].cost);
        rad[i] = i;
    }
}

bool cmp(matr a, matr b)
{
    if(a.cost < b.cost)
        return true;
    return false;
}

int grupa(int x)
{
    if(rad[x] == x)
        return x;
    rad[x] = grupa(rad[x]);
    return grupa(rad[x]);
}

void cauta(int x,int y)
{
    rad[grupa(x)] = grupa(y);
}

int main()
{
    int i,k=0,costul=0;
    citire();
    sort(v+1,v+m+1, cmp);
    for(i=1; i<=m; i++)
    {
        if(grupa(v[i].lin) != grupa(v[i].col))
        {
            k++;
            costul += v[i].cost;
            q.push_back(make_pair(v[i].lin,v[i].col));
            cauta(v[i].lin, v[i].col);
        }
    }
    fprintf(out, "%d\n%d\n", costul, k);
    for(i=0; i<k; i++)
        fprintf(out, "%d %d\n", q[i].first, q[i].second);
    return 0;
}