#include <fstream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;

class Kruskal {
public:
    int find_set(int x, vector<int>& parent) {
        if(parent[x] == -1)
            return x;
        return parent[x] = find_set(parent[x], parent);
    }

    void sets_union(int x, int y, vector<int>& parent, vector<int>& rank) {
        if(rank[x] < rank[y])
            swap(x, y);
        rank[x] += rank[y];
        parent[y] = x;
    }

    static bool comp(tuple<int,int,int> x, tuple<int,int,int> y) {
        return (get<2>(x) < get<2>(y));
    }

    void kruskal(vector<tuple<int,int,int>> edges, vector<pair<int,int>>& mst, vector<int>& parent, vector<int>& rank, int& cost) {
        sort(edges.begin(), edges.end(), comp);
        for(auto i: edges) {
            int x = find_set(get<0>(i), parent);
            int y = find_set(get<1>(i), parent);
            if(x != y) {
                sets_union(x, y, parent, rank);
                mst.push_back(make_pair(get<0>(i), get<1>(i)));
                cost += get<2>(i);
            }
        }
    }
};

int main()
{
    ifstream fin ("apm.in");
    ofstream fout("apm.out");

    int n, m, cost = 0;
    vector<tuple<int,int,int>> edges;
    
    fin >> n >> m;
    for(int i = 0; i < m; ++i) {
        int x, y, z;
        fin >> x >> y >> z;
        edges.push_back(make_tuple(x, y, z));
    }

    vector<pair<int,int>> mst;
    vector<int> parent(n + 1, -1), rank(n + 1, 1);

    Kruskal k;
    k.kruskal(edges, mst, parent, rank, cost);

    fout << cost << "\n" << n - 1 << "\n";
    for(auto i: mst) {
        fout << i.first << " " << i.second << "\n";
    }

    edges.clear(); 
    mst.clear(); 
    parent.clear(); 
    rank.clear();
    fin.close(); 
    fout.close();
    return 0;
}