#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
int N, M;
ifstream in("apm.in");
ofstream out("apm.out");


struct Edge {
    int start;
    int end;
    int cost;
    bool operator<(const Edge& ref) const {
        if (cost == ref.cost) {
            if (start == ref.start) {
                return end < ref.end;
            } else {
                return start < ref.start;
            }
        } else {
            return cost < ref.cost;
        }
    }
    Edge(int _start, int _end, int _cost) : start(_start), end(_end), cost(_cost)
    {

    }
    Edge(const Edge& ref) : start(ref.start), end(ref.end), cost(ref.cost)
    {

    }

};
vector<Edge> edges;
vector<int> apm_chosen_edges;
int apm_cost;
struct Forest {
    int parent;
    int idx;
    Forest() {}
    Forest(int p, int i) : parent(p), idx(i) {}
    Forest(const Forest& ref) : parent(ref.parent), idx(ref.idx) {}
};
vector<Forest> forests;
void read_input()
{
    in >> N >> M;
    for (int i = 0; i < M; i++) {
        int x,y,z;
        in >> x >> y >> z;
        edges.push_back(Edge(x,y,z));
    }

}
int forest_find(int x) {
    if (forests[x].parent != x) {
        forests[x].parent = forest_find(forests[x].parent);
    }
    
    return forests[x].parent;
}
void forest_union(int x, int y)
{
    if (forests[x].parent < forests[y].parent) {
        forests[y].parent = forest_find(x);
    } else {
        forests[x].parent = forest_find(y);
    }
}
void kruskal()
{
    sort(edges.begin(), edges.end());

    forests.resize(N+1);

    for (int i = 1; i <= N; i++) {
        forests[i].parent = i;
        forests[i].idx = i;
    }
    apm_cost = 0; 
    int apm_size = 1;
    for (int i = 0; i < edges.size(); i++) {
        Edge& current = edges[i];

//            cout << "Parent for " << current.start << " is " << forest_find(current.start) << "\n";
  //          cout << "Parent for " << current.end << " is " << forest_find(current.end) << "\n";
        if (forest_find(current.start) != forest_find(current.end)) {
            forest_union(current.start, current.end);
    //        cout << "Joined " << current.start << " with " << current.end << "\n";
            apm_cost += current.cost;
            apm_chosen_edges.push_back(i);
        }
    }
}
void print()
{
    out << apm_cost << "\n";
    out << apm_chosen_edges.size() << "\n";
    for (int i = 0; i < apm_chosen_edges.size(); i++) {
        int curIdx = apm_chosen_edges[i];
        out << edges[curIdx].start << " " << edges[curIdx].end << "\n";
    }
}
int main()
{

    read_input();
    kruskal();
    print();

    

}