#include<bits/stdc++.h>
#define in f
#define out g
using namespace std;

const int MAXN = 200100;

ifstream f("apm.in");
ofstream g("apm.out");

typedef struct Edge {
    int x;
    int y;
    int cost;
};

int father[MAXN];
vector<Edge> v;
vector<Edge> solution;
int n, m;

void read() {
    in >> n;
    in >> m;

    int x, y, z;
    for(int i = 1; i <= m; i++) {
        in >> x;
        in >> y;
        in >> z;

        Edge edge;
        edge.x = x;
        edge.y = y;
        edge.cost = z;

        v.push_back(edge);
    }

}

int getFather(int x) {
    while(father[x] != 0) {
        x = father[x];
    }

    return x;
}

void solve() {

    sort(v.begin(), v.end(), [](Edge a, Edge b) {
        return a.cost < b.cost;
    });

    int counter = 0;
    int cost = 0;

    while(counter < n - 1) {
        Edge current = v.front();
        if(getFather(current.x) != getFather(current.y)) {
            cost = cost + current.cost;
            counter++;
            father[current.x] = current.y;
            solution.push_back(current);
        }

        v.erase(v.begin());
    }

    out << cost << "\n" << counter << "\n";
    for(int i = 0; i < counter; i++){
        out << solution[i].x << " " << solution[i].y << "\n";
    }
}

int main() {
    read();
    solve();
    return 0;
}