#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>

const int MAX_DIST = 100000;
const int MIN_DIST = -100000;

using namespace std;

struct Edge {
    int n1, n2;

    Edge() {}
    Edge(int n1, int n2) : n1(n1), n2(n2) {}
};

struct NodeCost{
    int node, cost;

    NodeCost() {}
    NodeCost(int node, int cost) : node(node), cost(cost) {}
};


class mycomparison
{
public:
    bool operator() (const NodeCost& lhs, const NodeCost& rhs) const{
        return lhs.cost > rhs.cost;
    }
};


int main() {
    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout);
    int N, M, n1, n2, cost;
    scanf("%d%d", &N, &M);
    priority_queue<NodeCost, vector<NodeCost>, mycomparison> pq;
    vector<vector<NodeCost> > adj(N + 1);
    vector<int> dist(N + 1, MAX_DIST);
    vector<int> parent(N + 1, -1);
    vector<Edge> ama;
    int min_cost = 0;

    for (int i = 0; i < M; ++i) {
        scanf ("%d%d%d", &n1, &n2, &cost);
        adj[n1].push_back(NodeCost(n2, cost));
        adj[n2].push_back(NodeCost(n1, cost));
    }

    for (const NodeCost& nc : adj[1]) {
        dist[nc.node] = nc.cost;
        parent[nc.node] = 1;
        pq.push(nc);
    }
    N--;
    dist[1] = MIN_DIST;

    while (!pq.empty() && N != 0) {
        NodeCost nc;
        do {
            nc = pq.top();
            pq.pop();
        } while (!pq.empty() && dist[nc.node] == MIN_DIST);
        if (dist[nc.node] == MIN_DIST) {
            break;
        }
        N--;
        min_cost += dist[nc.node];
        ama.push_back(Edge(parent[nc.node], nc.node));
        dist[nc.node] = MIN_DIST;
        for (const NodeCost& n : adj[nc.node]) {
            if (dist[n.node] > n.cost) {
                dist[n.node] = n.cost;
                parent[n.node] = nc.node;
                pq.push(n);
            }
        }
    }

    printf("%d\n%lu\n", min_cost, ama.size());
    for (const Edge& edge : ama) {
        printf("%d %d\n", edge.n1, edge.n2);
    }
    return 0;
}