/*
 * =====================================================================================
 *
 *       Filename:  IA_APM.cpp
 *
 *    Description:  http://www.infoarena.ro/problema/apm
 *
 *        Version:  1.0
 *        Created:  04/04/2016 01:14:41 PM
 *       Revision:  none
 *       Compiler:  gcc/g++
 *
 *         Author:  Marius-Constantin Melemciuc 
 *          email: 
 *   Organization: 
 *
 * =====================================================================================
 */
 
#include <iostream>
#include <vector>
#include <utility>
#include <fstream>
#include <algorithm>
 
using namespace std;
 
vector<pair<pair<int, int>,
            int> > graph;
 
class DisjointDataSet {
    /**
     * The term rank is used instead of depth since it stops
     * being equal to the depth if path compression is also used.
     * Actually, rank is an upper bound on tree's height. 
     */
    vector<int> rank;
    vector<int> parent;
public:
    DisjointDataSet(int);
    ~DisjointDataSet();
    int getRoot(int);
    void link(int, int);
    void unionSets(int, int);
};
  
DisjointDataSet::DisjointDataSet(int n) {
    rank.resize(n + 1, 0);
    parent.resize(n + 1);
    for (int i = 0; i < n + 1; i++) {
        parent[i] = i;
    }
}
  
DisjointDataSet::~DisjointDataSet() {
}
  
int DisjointDataSet::getRoot(int x) {
    int i;
  
    for (i = x; parent[i] != i; i = parent[i]) {
    }
      
    // i is the root
    int aux;
    while (parent[x] != x) {  // path compression
        aux = parent[x];
        parent[x] = i;
        x = aux;
    }
    return i;
}
  
void DisjointDataSet::link(int x, int y) {
    if (rank[x] < rank[y]) {        // union by rank
        parent[x] = y;
    } else {
        if (rank[x] > rank[y]) {
            parent[y] = x;
        } else {
            parent[x] = y;
            rank[y]++;
        }
    }
}
  
void DisjointDataSet::unionSets(int x, int y) {
    link(getRoot(x), getRoot(y));
}
 
bool cmp(const pair<pair<int, int>, int>& a,
         const pair<pair<int, int>, int>& b) {
    if (a.second < b.second) {
        return true;
    }
    return false;
}
 
// O(MlogM) time
vector<pair<int, int> > getApmWithKruskal(vector<pair<pair<int, int>, int> > graph,
                                          int n,
                                          int& costApm) {
    sort(graph.begin(), graph.end(), cmp);
 
    DisjointDataSet d(n);
    vector<pair<int, int> > edgesOfApm;
    int x, y, cost;
    for (int i = 0; i < graph.size(); i++) {
        x = graph[i].first.first;
        y = graph[i].first.second;
        cost = graph[i].second;
 
        if (d.getRoot(x) != d.getRoot(y)) {
            edgesOfApm.push_back(make_pair(x, y));
            d.unionSets(x, y);
            costApm += cost;
        }   
    }
 
    return edgesOfApm;
}
 
int main() {
    ifstream in("apm.in");
    ofstream out("apm.out");
    int n, m;
 
    in >> n >> m;
 
    int x, y, cost;
    for (int i = 0; i < m; i++) {
        in >> x >> y >> cost;
        graph.push_back(make_pair(make_pair(x, y),
                                  cost));
    }
 
    int costApm = 0;
    vector<pair<int, int> > edgesApm = getApmWithKruskal(graph, n, costApm);
 
    out << costApm << "\n";
    out << edgesApm.size() << "\n";
 
    for (auto it = edgesApm.begin(); it != edgesApm.end(); it++) {
        out << it->first << " " << it->second << "\n";
    }
     
    in.close();
    out.close();
 
    return 0;
}