#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchii{
int a,b,c,bagat = 0;
} ma[400005];
int h[200001], tata[200001];
bool cmp(muchii a , muchii b) {
    if (a.c<b.c) {
        return true;
    }else {
        return false;
    }
}


void initializare(int i) {
    h[i] = 0;
    tata[i] = 0;
}

int reprezentant(int i) {
    while (tata[i]!=0)
    {i  = tata[i];}
    return i;
}
void uneste(int a , int b) {
    int ra = reprezentant(a);
    int rb = reprezentant(b);
    //if (h[ra]>h[rb]) {
        tata[rb] = ra;
    //}else {
        //tata[ra] = rb;
        //if (h[ra] == h[rb]) {
        //    h[rb]++;
        //}
    //}
}

int main()
{
    int n , m;
    fin>>n>>m;
    for (int i = 1;i<= m;i++) {
        fin>> ma[i].a >> ma[i].b >> ma[i].c;
    }
    sort(ma+1,ma+m+1,cmp);
/*
    for (int i = 1;i<= m;i++) {
        fout<< ma[i].a <<" "<<" "<< ma[i].b <<" " <<ma[i].c<<'\n';
    }
*/
    int cost = 0;
for (int i = 1 ; i<=m ; i++) {
    int c1 = ma[i].a ;
    int c2 = ma[i].b;
    if (reprezentant(c1)!=reprezentant(c2)) {
        cost = cost + ma[i].c;
        ma[i].bagat = 1;
    uneste(c1,c2);
    }
}
fout<< cost<<'\n';
    fout<< n-1<<'\n';
    for (int i = 1 ; i<=m;i++) {
        if (ma[i].bagat == 1) {
            fout<<ma[i].a<<" "<<ma[i].b<<'\n';
        }
    }
    return 0;
}