#include <iostream>
#include <fstream>
#include <list>
#include <queue>
#include <bits/stdc++.h>
#include <limits>

std::ifstream primin("apm.in");
std::ofstream primout("apm.out");

using namespace std;

class Link {
private:
    unsigned from;
    unsigned to;
    double cost;
public:
    Link(unsigned from, unsigned to, double cost): from(from), to(to), cost(cost) {}
    unsigned getTo() {
        return this->to;
    }

    double getCost() {
        return this->cost;
    }

};


class Graph {
private:
    unsigned V;
    std::list<Link> *adj;

public:
    Graph(unsigned V): V(V) {
        adj = new std::list<Link>[V + 1];
    }

    void addEdge(unsigned from, unsigned to, double cost) {
        Link first_link(from, to, cost);
        Link second_link(to, from, cost);
        adj[from].push_back(first_link);
        adj[to].push_back(second_link);
    }

    void Prim(unsigned start) {
        std::priority_queue<std::pair<double, unsigned>, std::vector<std::pair<double, unsigned>>, std::greater<>> pq;
        std::vector<int> key(this->V + 1, INT_MAX);
        std::vector<int> parent(this->V + 1, -1);
        std::vector<bool> inMST(this->V + 1, false);

        pq.push(std::make_pair(0, start));
        key[start] = 0;

        while(!pq.empty()) {
            unsigned u = pq.top().second;
            pq.pop();

            inMST[u] = true;

            for(auto it : adj[u]) {
                unsigned v = it.getTo();
                int cost = (int)it.getCost();
                if (inMST[v] == false && key[v] > cost) {
                    key[v] = cost;
                    pq.push(std::make_pair(key[v], v));
                    parent[v] = u;
                }
            }
        }
        int total_cost = 0;

        for(unsigned i = 1; i <= V; i ++) {
            total_cost += key[i];
        }
        primout << total_cost << std::endl;
        primout << V - 1 << std::endl;

        for (unsigned i = 2; i <= V; i ++)
            primout << parent[i] << " " << i << std::endl;
    }

};


int main() {
    int long n, m, a, b, c;
    primin >> n >> m;
    auto G = new Graph(n);
    for (unsigned i = 0; i < m; i ++) {
        primin >> a >> b >> c;
        G->addEdge(a, b, c);
    }
    G->Prim(1);

    return 0;
}