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

#define Nmax 200100
#define Mmax 400100

using namespace std;

class disjointSet {

    private:
        int size, father[Nmax], depth[Nmax];

        int root(int node) {

            if(node != father[node])
                father[node] = root(father[node]);
            else
                depth[node] = 2;

            return father[node];
        }

    public:
        void initialise(int Size) {
            size = Size;

            for(int i = 1; i <= size; i++) {
                father[i] = i;
                depth[i] = 1;
            }
        }

        void unite(int x, int y) {

            x = root(x);
            y = root(y);

            if(x == y)
                return;

            if(depth[x] < depth[y])
                father[x] = y;
            else
                father[y] = x;

            if(depth[x] == depth[y])
                depth[x]++;

            }

        bool same(int x, int y) {
            return (root(x) == root(y));
        }

} forest;

struct Edge {int A, B, Cost;} edge[Mmax];
vector <int> Solution;
int N, M, totalCost;

bool compareCost(Edge x, Edge y) {
    return x.Cost < y.Cost;
}
void Solve() {

    forest.initialise(N);
    sort(edge + 1, edge + M + 1, compareCost);

    for(int i = 1; i <= M; i++)
        if(!forest.same(edge[i].A, edge[i].B)) {
            forest.unite(edge[i].A, edge[i].B);
            totalCost += edge[i].Cost;
            Solution.push_back(i);
        }

}
void Read() {

    ifstream in("apm.in");
    in >> N >> M;

    for(int i = 1; i <= M; i++)
        in >> edge[i].A >> edge[i].B >> edge[i].Cost;

    in.close();
}
void Write() {

    ofstream out("apm.out");

    out << totalCost << '\n' << (N - 1) << '\n';

    for(int i = 0; i < N - 1; i++)
        out << edge[Solution[i]].A << ' ' << edge[Solution[i]].B << '\n';

    out.close();
}
int main() {

    Read();
    Solve();
    Write();

    return 0;
}