#include <bits/stdc++.h>
#define mp make_pair
using namespace std ;
const int NR = 200002 ;
const int NRM = 400001 ;
ifstream in ("apm.in") ;
ofstream out ("apm.out") ;

int parent[NR], rank_[NR];

struct Edge {
    int u, v, weight;
    bool operator<(Edge const& other) {
        return weight < other.weight;
    }
};


int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void make_set(int v) {
    parent[v] = v;
    rank_[v] = 0;
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rank_[a] < rank_[b])
            swap(a, b);
        parent[b] = a;
        if (rank_[a] == rank_[b])
            rank_[a]++;
    }
}



int main () {

    int n, m;
    vector<Edge> edges;
    in >> n >>m;
    for (int i =0; i <m; ++ i){
        Edge edge;
        in >>edge.u >>edge.v >> edge.weight;
        edge.u--, edge.v--;
        edges.emplace_back(edge);
    }


    int cost = 0;
    vector<Edge> result;

    sort(edges.begin(), edges.end());
    for (int i = 0; i < n; ++ i){
        make_set(i);
    }
    for (Edge e : edges) {
        int root1 = find_set(e.u);
        int root2 = find_set(e.v);
        if (root1 != root2) {
            cost += e.weight;
            result.push_back(e);
            union_sets(root1, root2);
        }
    }
    out << cost << '\n' << result.size() << '\n';
    for (auto e : result){
        out << e.u + 1 << ' ' << e.v + 1 << '\n';
    }
    return 0;
}