/******************************************************************************

Welcome to GDB Online.
  GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby, 
  C#, OCaml, VB, Perl, Swift, Prolog, Javascript, Pascal, COBOL, HTML, CSS, JS
  Code, Compile, Run and Debug online from anywhere in world.

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

using namespace std;

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

struct DSU {
    vector<int> T;
    
    DSU(int N) {
        T.resize(N + 1);
        iota(T.begin(), T.end(), 0);/// initializeaza T[i] = i
    }
    
    int find(int node) {
        if(node == T[node]) {
            return node;
        }
        return T[node] = find(T[node]);
    }
    
    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        T[a] = b;
    }
};

struct Edge {
    int x, y, c;
};

int main()
{
    int N, M;
    fin >> N >> M;
    DSU dsu(N);
    vector<Edge> edges(M);
    
    for(auto &[x, y, c] : edges) {
        fin >> x >> y >> c; ///echivalent cu edges[i].x, edges[i].y, edges[i].c
    }
    
    sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
       return a.c < b.c; 
    });
    
    int mst = 0;
    vector<Edge> ans;
    for(auto [x, y, c] : edges) {
        if(dsu.find(x) != dsu.find(y)) {
            mst += c;
            ans.push_back({x, y, c});
            dsu.unite(x, y);
        }
    }
    
    fout << mst << "\n" << ans.size() << "\n";
    for(auto [x, y, c] : ans) {
        fout << x << " " << y << "\n";
    }
    return 0;
}