#include <fstream>
#include <iostream>
#include <vector>
#include <cassert>
#include <cstring>
#include <set>
#include <unordered_map>
#include <memory>
#include <deque>
#include <queue>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <bitset>
 
using namespace std;
 
 
ifstream f("apm.in");
ofstream g("apm.out");

struct edge {
    int a, b, c;
};

bool cmpEdge(const edge& x, const edge& y) {
    return x.c < y.c;
}

void compress(int n, int p, vector<int>& parent) {
    for (; n != p; ) {
        int f = parent[n];
        parent[n] = p;
        n = f;
    }
}

int getset(int n, vector<int>& parent) {
    int p = n;

    while (parent[p] != p)
        p = parent[p];

    return p;
}

bool unite(int a, int b, vector<int>& parent, vector<int>& height) {
    int pa = getset(a, parent);
    int pb = getset(b, parent);

    if (pa == pb) {
        compress(a, pa, parent);
        compress(b, pb, parent);
        return false;
    }

    if (height[pa] > height[pb]) {
        swap(pa, pb);
        swap(a, b);
    }

    parent[pa] = pb;
    ++height[pb];
    compress(a, pb, parent);
    compress(b, pb, parent);

    return true;
}
 
int main() {
    int N, M;
    f >> N >> M;

    vector<int> parent(N), height(N);
    for (int i = 0; i < N; i++) {
        parent[i] = i;
        height[i] = 1;
    }

    vector<edge > edges(M);
    for (int i = 0; i < M; i++) {
        f >> edges[i].a >> edges[i].b >> edges[i].c;
    }
    sort(edges.begin(), edges.end(), &cmpEdge);

    int cost = 0;
    vector<edge> mst(N - 1);
    int ptr = 0;
    for (const edge& e : edges) {
        int a = e.a - 1;
        int b = e.b - 1;
        
        if (!unite(a, b, parent, height))
            continue;
        
        mst[ptr++] = e;
        cost += e.c;
    }

    g << cost << '\n' << N - 1 << '\n';
    for (const auto& e : mst)
        g << e.a << ' ' << e.b << '\n';
 
    f.close();
    g.close();
    return 0;
}