///KRUSKAL
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <algorithm>

using namespace std;

struct Node {
    int x, y, cost;
    Node(int x, int y, int cost) {
        this -> x = x;
        this -> y = y;
        this -> cost = cost;
    }
    Node() {}
};

bool comp(const Node& a, const Node& b) {return (a.cost < b.cost);}

int mFind(int x, vector<int>& s) {
    int c = x;
    while(c != s[c])
        c = s[c];
    s[x] = c;
    return c;
}

void mUnion(int x, int y, vector<int>& s, vector<int>& r) {
    int s1, s2;
    s1 = mFind(x, s);
    s2 = mFind(y, s);

    if(s1 == s2)
        return;

    if(r[s1] == r[s2]) {
        s[s2] = s1;
        ++r[s1];
    } else {
        if(r[s1] > r[s2])
            s[s2] = s1;
        else
            s[s1] = s2;
    }
}

int kruskal(vector<Node>& nodes, vector<int>& s, vector<int>& r, list<Node>& answ) {
    int totCost = 0;

    for(int i=0; i<nodes.size(); ++i) {
        if(mFind(nodes[i].x, s) == mFind(nodes[i].y, s))
            continue;

        mUnion(nodes[i].x, nodes[i].y, s, r);

        totCost += nodes[i].cost;
        answ.push_back(nodes[i]);
    }

    return totCost;
}

int main() {
    ifstream inStr("apm.in");
    ofstream outStr("apm.out");

    int N, M;
    inStr >> N >> M;

    vector<Node> nodes(M);

    int from, to, cost;
    for(int i=0; i<M; ++i) {
        inStr >> from >> to >> cost;
        nodes[i] = Node(--from, --to, cost);
    }

    sort(nodes.begin(), nodes.end(), comp);

    list<Node> answ;
    vector<int> s(N);
    vector<int> r(N, 0);

    for(int i=0; i<N; ++i)
        s[i] = i;

    int totCost = kruskal(nodes, s, r, answ);

    outStr << totCost << '\n';
    outStr << answ.size() << '\n';

    for(list<Node>::iterator it = answ.begin(); it != answ.end(); ++it)
        outStr << it -> x + 1 << ' ' << it -> y + 1 << '\n';

    return 0;
}