// Prim
#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct link {
    int nodeA;
    int nodeB;
    int value;
    bool operator< (const link& foreign) const {
        return this->value > foreign.value;
    }
};
bool cmp (const link& me, const link& foreign) {
    return me.value < foreign.value;
}

int E,V;

int main() {
    fin >> E >> V;
    vector<vector<link>> G(E+1);
    int cnt = 1;
    vector<link> _h;
    int startNodeA;
    vector<bool> vis(E+1, false);
    link startNode = {-1,-1,INT_MAX};
    for (int i = 1; i <= V; i++) {
        int nodeA, nodeB, weight;
        fin >> nodeA >> nodeB >> weight;
        G[nodeA].push_back({nodeA,nodeB,weight});
        G[nodeB].push_back({nodeB,nodeA,weight});
        if (startNode.value > weight) {
            startNode = {nodeA, nodeB, weight};
        } else if (startNode.value == weight && startNode.nodeA > nodeA) {
            startNode = {nodeA, nodeB, weight};
        }
    }

    for (auto& i: G[startNode.nodeA]) {
        if (vis[i.nodeB]) {
            continue;
        }
        _h.push_back(i);
        push_heap(_h.begin(), _h.end());
    }
    vis[startNode.nodeA] = true;
    make_heap(_h.begin(),_h.end());
    queue<link>ans;
    long long cnt_ans = 0;
    while (cnt < E) {
        if (!_h.empty()) {
            ans.push(_h.front());
            int _node = _h.front().nodeB;
            cnt_ans += _h.front().value;
            pop_heap(_h.begin(), _h.end());
            _h.pop_back();
            vis[_node] = true;
            cnt++;
            for (auto& k: G[_node]) {
                if (!vis[k.nodeB]) {
                    _h.push_back(k);
                    push_heap(_h.begin(), _h.end());
                }
            }

            while (!_h.empty() && vis[_h.front().nodeB]) {
                pop_heap(_h.begin(), _h.end());
                _h.pop_back();
            }
        }
    }
    fout << cnt_ans << '\n';
    fout << ans.size() << '\n';
    while (!ans.empty()) {
        fout << ans.front().nodeA << ' ' << ans.front().nodeB << '\n';
        ans.pop();
    }

    return 0;
}





// Kruskal
/*
#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct vertex {
    int edge;
    int weight;
};
struct complete_vertex {
    int edgeA;
    int edgeB;
    int weight;
    bool operator<(const complete_vertex& foreign) const {
        return this->weight > foreign.weight;
    }
};

int E,V;
vector<int> T;

int getRoot(int node) {
    int _node = node;
    while (T[node] > 0) {
        node = T[node];
    }
    while(_node != node) {
        const int aux = T[_node];
        T[_node] = node;
        _node = aux;
    }
    return node;
}

void join(int edgeA, int edgeB){
    const int rootA = getRoot(edgeA);
    const int rootB = getRoot(edgeB);
    if (rootA > rootB) {
        T[rootB] += T[rootA];
        T[rootA] = rootB;
    } else {
        T[rootA] += T[rootB];
        T[rootB] = rootA;
    }

}

int main() {
    fin >> E >> V;
    T.assign(E+1, -1);
    long long ans_weight = 0;
    vector<forward_list<vertex>> G(E+1);
    priority_queue<complete_vertex> pq;
    queue<vertex> ans;
    for (int i = 1; i <= V; i++) {
        int edgeA, edgeB, value;
        fin >> edgeA >> edgeB >> value;
        G[edgeA].push_front({edgeB, value});
        pq.push({edgeA, edgeB, value});
    }
    while(!pq.empty()) {
        const complete_vertex curr = pq.top();
        const int rootA = getRoot(curr.edgeA);
        const int rootB = getRoot(curr.edgeB);
        if (rootA == rootB);
        else {
            join(curr.edgeA, curr.edgeB);
            ans_weight += curr.weight;
            ans.push({curr.edgeA,curr.edgeB});
        }
        pq.pop();
    }
    fout << ans_weight << '\n';
    fout << ans.size() << '\n';
    while (!ans.empty()) {
        fout << ans.front().edge << ' ' << ans.front().weight << '\n';
        ans.pop();
    }
    return 0;
}
*/