//
//  main.cpp
//  C++ - teste
//
//  Created by Filip Cuciuc on 03/02/2020.
//  Copyright © 2020 Filip Cuciuc. All rights reserved.
//

//#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <map>
#include <string>
#include <cctype>
//#include "MED.h"
using namespace std;
//using namespace std::chrono;

ifstream cin("apm.in");
ofstream cout("apm.out");
const int MAXNODE = 2e5;
const int MAXEDGEs = 4e5;
struct node {
    int x, y, c;
} nod[MAXEDGEs];

bool cmp(node a ,node b){
    return a.c < b.c;
}

int n, m, ans;
int tata[MAXNODE], card[MAXNODE];

void read() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> nod[i].x >> nod[i].y >> nod[i].c;
    }
}

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

void unite(int a, int b) {
    if(card[a] == card[b]){
        tata[a] = b;
        card[a]++;
    }
    else if(card[a] < card[b]){
        tata[a] = b;
    }
    else{
        tata[b] = a;
    }
}

void solve() {
    read();
    sort(nod + 1, nod + m + 1, cmp);
    vector < node > rez;
    for (int i = 1; i <= m; i++) {
        node now = nod[i];
        int x, y;
        x = hasFather(now.x);
        y = hasFather(now.y);
        if (x != y) {
            unite(x, y);
            rez.push_back(now);
            ans += now.c;
        }
    }
    cout << ans << '\n' << rez.size() << '\n';
    for (auto& x : rez) {
        cout << x.x << " " << x.y << '\n';
     }
}
 
int main() {
    
    solve();
    
    return 0;
}