#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int n,m,total;

const int grafSize = 400005;

pair<int, int> arbore[grafSize];
int arboreSize;
vector<int> tata(grafSize);
vector<int> rang(grafSize);

struct muchie {
    int x, y, cost;
};

vector<muchie> graf;

bool compare(muchie m1, muchie m2) {
    return m1.cost < m2.cost;
}

void read() {
    ifstream in("dfs.in");
    in >> n >> m;
    muchie m2;
    m2.x = 0;
    m2.y = 0;
    m2.cost = 0;
    graf.push_back(m2);
    for(int i = 1; i <= m; i++) {
        muchie m1;
        in >> m1.x >> m1.y >> m1.cost;
        graf.push_back(m1);
    }
    for(int i = 1; i <= n; i++) {
        tata[i] = i;
        rang[i] = 1;
    }
    sort(graf.begin() + 1, graf.end(), compare);
}

int find(int node) {
    while (tata[node] != node) {
        node = tata[node];
    }
    return node;
}

void merge(int x, int y) {
    if(rang[x] < rang[y])
        tata[x] = y;
    if(rang[x] > rang[y])
        tata[y] = x;
    if(rang[x] == rang[y])
        tata[x] = y, rang[y]++;
}

void solve() {
    for(int i = 1; i <= m; i++) {
        int find_x = find(graf[i].x);
        int find_y = find(graf[i].y);
        if(find_x != find_y) {
            merge (find_x, find_y);
            arbore[++arboreSize].first = graf[i].x;
            arbore[arboreSize].second = graf[i].y;
            total += graf[i].cost;
        }

    }
}

int main() {
    read();
    solve();
    ofstream out("dfs.out");
    out << total << endl;
    out << arboreSize << endl;
    for(int i = 1; i <= arboreSize; i++) {
        out << arbore[i].first << " " << arbore[i].second << endl;
    }
    return 0;
}