#include <bits/stdc++.h>
#define dimn 200005
#define dimm 400005
#define mp std::make_pair
#define cost first
#define index second
struct data {
    int x, y, cost;
    bool operator < (const data& obj) {
        return cost < obj.cost;
    }
};

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

int N, M;
int padure[dimn];
data edge[dimm];
std::vector <int> sol;

int find(int nod) {
    if(padure[nod] == nod) return nod;
    return find(padure[nod]);
}
int unite(int x, int y) {
    padure[find(x)] = find(y);
}

void citire() {
    f >> N >> M;
    for (int i=1; i<=N; i++)
        padure[i] = i;
    for (int i=1, y, x, c; i<=M; i++)
        f >> edge[i].y >> edge[i].x >> edge[i].cost;
}
void rezolvare() {
    std::sort(edge+1, edge+M+1);
    long long ans = 0;
    for (int i=1, x, y; i<=M; i++) {
        x = edge[i].x; y = edge[i].y;
        if(find(x) != find(y)) {
            ans += 1LL*edge[i].cost;
            unite(x, y);
            sol.push_back(i);
        }
    } g << ans << "\n" << sol.size() << "\n";
    for (int i=0; i<sol.size(); i++)
        g << edge[sol[i]].x << " " << edge[sol[i]].y << "\n";
}

int main()
{
    citire();
    rezolvare();

    return 0;
}