#include <bits/stdc++.h>

using namespace std;

struct Node {
    int key, parent = -1, nodeId;
    bool inQueue;
    bool operator<(const Node& other) const
    {
        return key > other.key;
    }
};

vector<vector<pair<int, int>>> adj; // u -> (v, w)

int V, E;

ifstream in;
ofstream out;

void addEdge(int u, int v, int w)
{
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
}

void mst_Prim(int r) {
    vector<Node> nodes(V+1);
    for (int i = 1; i <= V; i++)
    {
        nodes[i] = {INT_MAX, -1, i, true};
    }
    nodes[r].key = 0;
    priority_queue<Node, vector<Node>> q;
    q.push(nodes[r]);
    while (!q.empty()) {
        int u = q.top().nodeId;
        q.pop();
        nodes[u].inQueue = false;
        for (auto [v, w] : adj[u])
        {
            if (nodes[v].inQueue && w < nodes[v].key)
            {
                nodes[v].parent = u;
                nodes[v].key = w;
                q.push(nodes[v]);
            }
        }
    }
    int cost = 0;
    for (int i = 1; i <= V; i++) {
            cost += nodes[i].key;
    }
    out << cost << '\n';
    out << V-1 << '\n';
    for (int i = 1; i <= V; i++) {
        if (nodes[i].parent != -1)
            out << nodes[i].parent << ' ' << i << endl;
    }
}

int main(int argc, char** argv)
{
    in.open("apm.in");
    out.open("apm.out");
    auto start = chrono::high_resolution_clock::now();

    in >> V >> E;
    adj.reserve(V + 1);

    for(int i = 0; i < E; i++)
    {
        int u, v, w;
        in >> u >> v >> w;
        addEdge(u, v, w);
    }
    mst_Prim(1);
    auto end = chrono::high_resolution_clock::now();
    auto dif = chrono::duration_cast<chrono::milliseconds> (end - start);
    cout << "Time: " << dif.count() << "ms" << endl;
}