#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int maxn = 2e5;
const int maxm = 4e5;
struct child {
    int node, cost;

    child(int node = 0, int cost = 0) {
        this->node = node;
        this->cost = cost;
    }
};
struct muchie {
    int u, v, cost;
    muchie(int u = 0, int v = 0, int cost = 0) {
        this->u = u;
        this->v = v;
        this->cost = cost;
    }
    bool operator<(const muchie &a) const {
        return cost > a.cost;
    }
};
vector<child> adj[maxn + 1];
bool visited[maxn + 1];

int main() {
    int n, m;
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, cost;
        fin >> u >> v >> cost;
        adj[u].push_back(child(v, cost));
        adj[v].push_back(child(u, cost));
    }

    int cost = 0;
    vector<muchie> arbore;
    priority_queue<muchie> goolah;
    goolah.push(muchie(0, 1, 0));
    while (arbore.size() < n) {
        muchie curr = goolah.top();
        goolah.pop();
        if (visited[curr.v])
            continue;
        visited[curr.v] = true;
        arbore.push_back(curr);
        cost += curr.cost;
        for (child elem: adj[curr.v])
            goolah.push(muchie(curr.v, elem.node, elem.cost));
    }

    fout << cost << '\n' << n - 1 << '\n';
    vector<muchie>::iterator itr = arbore.begin();
    while ((++itr) != arbore.end())
        fout << itr->u << ' ' << itr->v << '\n';

    return 0;
}