#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define FILEIN "apm.in"
#define FILEOUT "apm.out"
#define NMAX 200005
#define MMAX 400005

struct Muchie {
    int x;
    int y;
    int cost;

    Muchie(int _x = 0, int _y = 0, int _cost = 0) {
        this->x = _x, this->y = _y, this->cost = _cost;
    };

    bool operator<(const Muchie& other) const {
        return this->cost < other.cost;
    }
};

int Set[NMAX], Rank[NMAX], N, M;
Muchie E[NMAX];

int findSet(int x) {
    if (Set[x] == x)
        return x;

    return (Set[x] = findSet(Set[x]));
}

void uniteSet(int x, int y) {
    int xRoot = findSet(x), yRoot = findSet(y);

    if (xRoot == yRoot)
        return;

    if (Rank[xRoot] < Rank[yRoot])
        Set[xRoot] = yRoot;
    else
        Set[yRoot] = xRoot;
    if (Rank[xRoot] == Rank[yRoot])
        Rank[yRoot]++;
}

int main() {
    freopen(FILEIN, "r", stdin);
    freopen(FILEOUT, "w", stdout);

    scanf("%d %d", &N, &M);

    for ( int i = 1, x, y, c; i <= M; i++ ) {
        scanf("%d %d %d", &x, &y, &c);

        E[i] = Muchie(x, y, c);
    }

    for ( int i = 1; i <= N; i++ ) Set[i] = i;

    int Selected = 0, Solution = 0;
    vector<int> SolEdges;

    sort(E+1, E+M+1);

    for ( int i = 1; i <= M && Selected != N-1; i++ ) {
        if (findSet(E[i].x) != findSet(E[i].y)) {
            Selected++;
            Solution += E[i].cost;
            SolEdges.push_back(i);

            uniteSet(E[i].x, E[i].y);
        }
    }

    printf("%d\n", Solution);
    printf("%d\n", SolEdges.size());
    for ( int i = 0; i <SolEdges.size(); i++ ) {
        printf("%d %d\n", E[SolEdges[i]].x, E[SolEdges[i]].y);
    }

    return 0;
}