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

// Disjoint set data struture
class DSU {
    vector<int> parent, rank;

public:
    DSU(int n) {
        parent.resize(n);
        rank.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    int find(int i) {
        return (parent[i] == i) ? i : (parent[i] = find(parent[i]));
    }

    void unite(int x, int y) {
        int s1 = find(x), s2 = find(y);
        if (s1 != s2) {
            if (rank[s1] < rank[s2]) parent[s1] = s2;
            else if (rank[s1] > rank[s2]) parent[s2] = s1;
            else parent[s2] = s1, rank[s1]++;
        }
    }
};
bool comparator(vector<int> &a,vector<int> &b){
   return a[2] < b[2]; 
}
pair<vector<vector<int>>,int> kruskalsMST(int V, vector<vector<int>> &edges) {
    
    // Sort all edges
    sort(edges.begin(), edges.end(),comparator);
    
    // Traverse edges in sorted order
    DSU dsu(V);
    int cost = 0, count = 0;
    
    vector<vector<int>> arb;

    for (auto &e : edges) {
        int x = e[0], y = e[1], w = e[2];
        
        // Make sure that there is no cycle
        if (dsu.find(x) != dsu.find(y)) {
            
            arb.push_back(e);
            dsu.unite(x, y);
            cost += w;
            if (++count == V - 1) break;
        }
    }
    return make_pair(arb,cost);
}

int main() {
    
    
    vector<vector<int>> edges;
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n,m;
    fin>>n>>m;
    int n1,n2,w;
    while(fin>>n1>>n2>>w){
        vector<int> element;
        element.push_back(n1);
        element.push_back(n2);
        element.push_back(w);
        // cout<<element[0]<<" "<<element[1]<<" "<<element[2]<<"\n";
        edges.push_back(element);
    }
    // cout<<kruskalsMST(m, edges)<<endl;
    auto result = kruskalsMST(m, edges);
    fout<<result.second<<"\n";
    fout<<result.first.size()<<"\n";
    for(auto &edge : result.first){
        fout<<edge[1]<<" "<<edge[0]<<"\n";  
    }
    return 0;
}