/*
Alexandru Enache
Grupa 252
*/

#include <bits/stdc++.h>
using namespace std;

//ifstream fin("input"); ofstream fout("output");
ifstream fin("apm.in"); ofstream fout("apm.out");

class Graph{

private:

    int m_nodes;
    vector < vector < int > > m_gr;
    vector < int > m_disjointParent, m_disjointCardinal;

    vector < pair < int, pair < int , int > > > m_weighted_edges;


    void dfs(int node, vector < bool > &used){
        used[node] = true;
        for (auto &x: m_gr[node]){
            if (!used[x]){
                dfs(x, used);
            }
        }
    }

    void dfs_biconexe (int nod , int dad, vector < int > &lv, vector < int > &MIN, stack < int > &s, vector < vector < int > > &ans){
        lv[nod] = lv[dad]+1;
        MIN[nod] = lv[nod];
        s.push(nod);
        for (auto &x : m_gr[nod]){
            if (lv[x]){
                if (x != dad){
                    MIN[nod] = min(MIN[nod] , lv[x]);
                }
            }
            else{
                dfs_biconexe(x , nod, lv, MIN, s, ans);
                MIN[nod] = min(MIN[nod] , MIN[x]);
                if (MIN[x] >= lv[nod]){
                    vector < int > aux;
                    while (s.top() != x){
                        aux.push_back(s.top());
                        s.pop();
                    }
                    aux.push_back(x);
                    s.pop();
                    aux.push_back(nod);
                    ans.push_back(aux);
                }
            }
        }
    }

    void dfs_ctc(int nod, vector < vector < int > > &gr, vector < bool > &used, vector < int > &aux){
        used[nod] = true;
        for (auto& x : gr[nod]) {
            if (!used[x]) {
                dfs_ctc(x, gr, used, aux);
            }
        }
        aux.push_back(nod);
    }


public:

    Graph(){
        m_nodes = 0;
        m_gr = {};
    }

    Graph(int nodes, vector < vector < int > > &gr){
        m_nodes = nodes;
        m_gr = gr;

        m_disjointParent.resize(nodes+1);
        m_disjointCardinal.resize(nodes+1);

        for (int i=1; i<=nodes; i++) {
            m_disjointParent[i] = i;
            m_disjointCardinal[i] = 1;
        }
    }

    Graph(int nodes, vector < pair < int, pair < int , int >  > > &weighted_edges){
        m_nodes = nodes;
        m_weighted_edges = weighted_edges;

        m_disjointParent.resize(nodes+1);
        m_disjointCardinal.resize(nodes+1);

        for (int i=1; i<=nodes; i++) {
            m_disjointParent[i] = i;
            m_disjointCardinal[i] = 1;
        }
    }


    vector < int > bfs(int start){
        queue < int > q;
        vector < int > dist(m_nodes + 1, -1);

        dist[start] = 0;
        q.push(start);

        while (!q.empty()){
            int now = q.front();
            q.pop();

            for (auto &x : m_gr[now]){
                if (dist[x] == -1){
                    dist[x] = dist[now] + 1;
                    q.push(x);
                }
            }
        }

        return dist;
    }

    int comp_conexe(){

        int cont = 0;
        vector < bool > used(m_nodes + 1, false);
        for (int i=1; i<=m_nodes; i++){
            if (!used[i]){
                dfs(i, used);
                cont++;
            }
        }

        return cont;
    }

    vector < vector < int > > comp_biconexe(){

        vector < vector < int > > ans;

        vector < int > lv (m_nodes + 1, 0);
        vector < int > MIN (m_nodes + 1, 0);
        stack < int > s;

        for (int i=1; i<=m_nodes; i++){
            if (!lv[i]){
                dfs_biconexe(i , 0, lv, MIN, s, ans);
                while (!s.empty()) s.pop();
            }
        }

        return ans;
    }

    vector < vector < int > > ctc(){

        vector < vector < int > > ans;

        vector < bool > used(m_nodes + 1, false);
        vector < int > ord;

        for (int i=1; i<=m_nodes; i++) if (!used[i]) dfs_ctc(i, m_gr, used, ord);

        reverse(ord.begin(), ord.end());

        vector < vector < int > > inv(m_nodes + 1);

        for (int i=1; i<=m_nodes; i++){
            used[i] = false;
            for (auto &x : m_gr[i]){
                inv[x].push_back(i);
            }
        }

        for (auto &x: ord){
            if (!used[x]){
                vector < int > aux;
                dfs_ctc(x, inv, used, aux);
                ans.push_back(aux);
            }
        }

        return ans;
    }

    vector < int > ord_topologica(){

        vector < bool > used(m_nodes + 1, false);
        vector < int > ord;

        for (int i=1; i<=m_nodes; i++) if (!used[i]) dfs_ctc(i, m_gr, used, ord);

        reverse(ord.begin(), ord.end());

        return ord;
    }

    bool Havel_Hakimi(vector < int > v){

        for (int i=0; i<v.size(); i++){
            sort(v.begin(), v.end());
            reverse(v.begin(), v.end());

            if (v[0] > (int)v.size()-1) return false;

            for (int j=1; j<=v[0]; j++){
                v[j]--;
                if (v[j] < 0) return false;
            }
            v[0] = 0;
        }

        return true;
    }

    //disjoint
    int disjoint_find_parent(int node){
        if (node != m_disjointParent[node]) {
            m_disjointParent[node] = disjoint_find_parent(m_disjointParent[node]);
        }
        return m_disjointParent[node];
    }

    void disjoint_unite(int node_A, int node_B) {
        node_A = disjoint_find_parent(node_A);
        node_B = disjoint_find_parent(node_B);
        if (m_disjointCardinal[m_disjointParent[node_A]] > m_disjointCardinal[m_disjointParent[node_B]]) {
            int old_value = m_disjointCardinal[m_disjointParent[node_B]];
            m_disjointParent[node_B] = m_disjointParent[node_A];
            m_disjointCardinal[m_disjointParent[node_A]] += old_value;
        }
        else {
            int old_value = m_disjointCardinal[m_disjointParent[node_A]];
            m_disjointParent[node_A] = m_disjointParent[node_B];
            m_disjointCardinal[m_disjointParent[node_B]] += old_value;
        }
    }

    //minimum spanning tree
    vector < pair <int , pair < int , int > > > minimum_spanning_tree(){
        vector < pair <int , pair < int , int > > > answer;

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

        for (auto &x : m_weighted_edges){
            if (disjoint_find_parent(x.second.first) != disjoint_find_parent(x.second.second)){
                answer.push_back(x);
                disjoint_unite(x.second.first, x.second.second);
            }
        }

        return answer;
    }


};


void solve() {

    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n, m;
    fin >> n >> m;

    vector < pair < int , pair < int , int > > > weighted_edges;

    for (int i=1; i<=m; i++){
        int node_A, node_B, value;
        fin>>node_A>>node_B>>value;
        weighted_edges.push_back({value, {node_A, node_B}});
    }

    Graph graph = Graph(n, weighted_edges);

    vector < pair < int , pair < int , int > > > answer = graph.minimum_spanning_tree();

    int cont = 0;
    for (auto &x: answer){
        cont += x.first;
    }

    fout<<cont<<'\n';
    fout<<answer.size()<<'\n';
    for (auto &x: answer){
        fout<<x.second.first<<" "<<x.second.second<<'\n';
    }

}


int main() {

    solve();

    return 0;
}