#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MMAX = 400001;
const int NMAX = 200001;
struct muchii{
    int n1;
    int n2;
    int c;
}G[MMAX];
int dad[NMAX];
void makeSet(int n){
    for(int i=1;i<=n;i++)
        dad[i] = i;
}
int boss(int slave){
    if(slave != dad[slave])
        dad[slave] = boss(dad[slave]);
    return dad[slave];
}
void unite(int x, int y){
    int r1 = boss(x);
    int r2 = boss(y);
    dad[r1] = r2;
}
bool cmp(muchii a, muchii b){
    if(a.c < b.c)
        return 1;
    return 0;
}
vector <pair<int, int> > solution;
int main()
{
    FILE *fin, *fout;
    int n,m,i,cost;
    fin = fopen("apm.in","r");
    fout = fopen("apm.out","w");
    fscanf(fin,"%d %d",&n,&m);
    for(i=1;i<=m;i++)
        fscanf(fin,"%d %d %d",&G[i].n1, &G[i].n2, &G[i].c);
    sort(G + 1, G + m + 1, cmp);
    makeSet(n);
    cost = 0;
    for(i=1;i<=m;i++){
        if(boss(G[i].n1) != boss(G[i].n2)){
            cost += G[i].c;
            unite(G[i].n1,G[i].n2);
            solution.push_back(make_pair(G[i].n1,G[i].n2));
        }
    }
    fprintf(fout,"%d\n%d\n",cost,solution.size());
    pair <int, int> cuplu;
    while(!solution.empty()){
        cuplu = solution.back();
        fprintf(fout,"%d %d\n",cuplu.first,cuplu.second);
        solution.pop_back();
    }
    fclose(fin);
    fclose(fout);
    return 0;
}