#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <set>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

struct muchie {
    int x, y, cost;

    muchie(int _x, int _y, int _cost) : x(_x), y(_y), cost(_cost) {}
};

bool operator<(const muchie &a, const muchie &b) {
    if (a.cost == b.cost)
        return a.x < b.x;
    return a.cost < b.cost;
}

void add_vecin(int nod, auto& vecin, auto& cost, auto& Set, auto& visited) {
    visited[nod] = true;
    for (int i = 0; i < vecin[nod].size(); i++) {
        if (visited[vecin[nod][i]] == true)
            continue;

        Set.insert(muchie(nod, vecin[nod][i], cost[nod][i]));
    }
}

int main() {
    int n, m;
    in >> n >> m;

    vector<vector<int>> vecin(n);
    vector<vector<int>> cost(n);

    for (int i = 0; i < m; i++) {
        int x, y, c;
        in >> x >> y >> c;
        x--; y--;

        vecin[x].push_back(y);
        vecin[y].push_back(x);
        cost[x].push_back(c);
        cost[y].push_back(c);
    }

    set<muchie> Set;

    int total_cost = 0;
    vector<muchie> ans;
    vector<bool> visited(n, false);
    add_vecin(0, vecin, cost, Set, visited);

    while (!Set.empty()) {
        if (ans.size() == n - 1)
            break;

        muchie A = *Set.begin();
        Set.erase(Set.begin());

        if (visited[A.y])
            continue;

        ans.push_back(A);
        total_cost += A.cost;

        add_vecin(A.y, vecin, cost, Set, visited);
    }

    out << total_cost << '\n';
    out << ans.size() << '\n';
    for (auto i : ans) {
        out << ++i.x << " " << ++i.y << '\n';
    }


    return 0;
}