#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int NMax = 2 * 1e5;

struct Edge{
    int node1, node2, cost;
    bool operator < (const Edge other) const{
        return cost < other.cost;
    }
};
vector <Edge> edges, answer;
int n, m, cost;
int father[NMax + 5], height[NMax + 5];

void Read(){
    fin >> n >> m;
    while (m--){
        int x, y, c;
        fin >> x >> y >> c;
        edges.push_back({x, y, c});
    }
}

int Root(int node){
    while (father[node])
        node = father[node];
    return node;
}

int Check(int node1, int node2){
    int root1, root2;
    root1 = Root(node1);
    root2 = Root(node2);
    if (root1 == root2)
        return 1;
    return 0;
}

void Join(int node1, int node2){
    int root1, root2;
    root1 = Root(node1);
    root2 = Root(node2);
    if (height[root1] < height[root2]){
        father[root1] = root2;
        height[root2] = max(height[root2], height[root1] + 1);
    }
    else{
        father[root2] = root1;
        height[root1] = max(height[root1], height[root2] + 1);
    }
}

void Solve(){
    sort(edges.begin(), edges.end());
    for (auto edge : edges)
        if (!Check(edge.node1, edge.node2)){
            cost += edge.cost;
            Join(edge.node1, edge.node2);
            answer.push_back(edge);
        }
}

void Print(){
    fout << cost << '\n';
    fout << answer.size() << '\n';
    for (auto edge : answer)
        fout << edge.node1 << ' ' << edge.node2 << '\n';
}

int main(){
    Read();
    Solve();
    Print();
    return 0;
}