#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int nmx = 200002;
const int mmx = 400002;

int n,m,sum,rang[nmx],tata[nmx],total[nmx],t;
pair<int,pair<int,int> > e[mmx];
pair <int,int> r[nmx];

void citire(){
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; ++i)
        scanf("%d %d %d", &e[i].second.first, &e[i].second.second, &e[i].first);
}

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

void uneste(int g1, int g2){
    if(rang[g1] > rang[g2])
        tata[g2] = tata[g1];
    else
        tata[g1] = tata[g2];
    if(rang[g2] == rang[g1])
        ++ rang[g2];
}

void apm(){
    for(int i = 1; i <= n; ++i)
        tata[i] = i;
    int g1,g2;
    for(int i = 1; i <= m && t < n - 1; ++i){
        g1 = da_grup(e[i].second.first);
        g2 = da_grup(e[i].second.second);
        if(g1 != g2){
            uneste(g1,g2);
            r[++t].first = e[i].second.first;
            r[t].second = e[i].second.second;
            sum += e[i].first;
        }
    }
}

void afish(){
    printf("%d\n", sum);
    printf("%d\n", n-1);
    for(int i = 1; i < n; ++i)
        printf("%d %d\n", r[i].first, r[i].second);
}

int main() {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    citire();
    sort(e+1,e+m+1);
    for(int i = 1; i <= n; ++i){
        rang[i] = i;
        tata[i] = i;
    }
    apm();
    afish();
    return 0;
}