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

#define pair pair<int, int>

using namespace std;

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

const int NM = 200010;

struct Edge {
    int X, Y, C;
};

int T[NM];
vector <Edge> G;
vector <pair> MST;
int N, E, i, cost;

bool cmp(Edge x, Edge y) {
    return (x.C < y.C);
}

void Merge(int x, int y) {
    T[y] = x;
}

int FindSet(int node) {
    if (T[node] != node)
        T[node] = FindSet(T[node]);
    return T[node];
}

void Solve() {
    sort(G.begin(), G.end(), cmp);

    for (auto &it: G) {
        Edge crt = it;
        int set_X = FindSet(crt.X);
        int set_Y = FindSet(crt.Y);
        if (set_X != set_Y) {
            Merge(set_X, set_Y);
            cost += crt.C;
            MST.push_back({crt.X, crt.Y});
        }
    }
}

int main()
{
    in >> N >> E;
    for (i = 1; i <= E; ++i) {
        Edge e;
        in >> e.X >> e.Y >> e.C;
        G.push_back(e);
    }

    for (i = 1; i <= N; ++i) {
        T[i] = i;
    }

    Solve();

    out << cost << '\n' << MST.size() << '\n';
    for (auto &it: MST) {
        out << it.first << ' ' << it.second << '\n';
    }

    return 0;
}