#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>

using namespace std;

#define INFILE "apm.in"
#define OUTFILE "apm.out"

struct DSU {

public:
    vector<int> sz;
    vector<int> parent;

    DSU(){}
    DSU(int _n) {
        sz.resize(_n + 1, 1);
        parent.resize(_n + 1);
        for(int i = 1; i <= _n; ++i) parent[i] = i;
    }

    int findParent(int node){
        if(parent[node] == node) return node;
        return parent[node] = findParent(parent[node]);
    }

    bool sameSet(int node1, int node2){
        return (findParent(node1) == findParent(node2));
    }

    void mergeSets(int node1, int node2){
        node1 = findParent(node1);
        node2 = findParent(node2);
        if(node1 == node2) return;
        if(sz[node1] < sz[node2]) swap(node1, node2);
        sz[node1] += sz[node2];
        parent[node2] = node1;
    }

};

struct Edge {

public:
    int left;
    int right;
    int cost;

    Edge() : left(-1), right(-1), cost(-1) {}
    Edge(int _left, int _right, int _cost) : left(_left), right(_right), cost(_cost) {}

    bool operator<(const Edge &other) const {
        return (this -> cost < other.cost);
    }

};

int n, m;
vector<Edge> edges;

void solve(){

    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int node, to, cost; cin >> node >> to >> cost;
        edges.push_back(Edge(node, to, cost));
    }

    sort(edges.begin(), edges.end());

    int costTotal = 0;
    vector<pair<int, int> > ans;
    DSU dsu(n);

    for(auto &it : edges){
        if(!dsu.sameSet(it.left, it.right)){
            dsu.mergeSets(it.left, it.right);
            costTotal += it.cost;
            ans.push_back(make_pair(it.left, it.right));
        }
    }

    cout << costTotal << '\n';
    cout << ans.size() << '\n';
    for(auto &it : ans){
        cout << it.first << " " << it.second << '\n';
    }

}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);
    solve();
    return 0;
}