#include<bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int MMax = 400000;
const int NMax = 200000;

int N, M, TT[NMax+5], Sol, R[NMax+5];

struct Muchie {
    int x, y, c;
    bool use;
}E[MMax+5];

bool cmp(Muchie a,Muchie b) {
    return (a.c < b.c);
}

void ReadandSort() {
    in >> N >> M;
    for (int i = 0; i < M; i++) {
        in >> E[i].x >> E[i].y >> E[i].c;
    }

    sort(E,E+M,cmp);
}

int Root(int x) {
    while(TT[x] != x)
        x = TT[x];
    return x;
}

void Unite(int x, int y) {
    if(R[x] < R[y])
        TT[x] = y;
    if(R[x] > R[y])
        TT[y] = x;
    if(R[x] == R[y]) {
        TT[y] = x;
        R[x]++;
    }
}

void Solve() {
    for (int i = 1; i <= N; i++)
        TT[i] = i;
    for (int i = 0; i < M; i++) {
        int a = Root(E[i].x);
        int b = Root(E[i].y);
        if (a != b) {
            Unite(a,b);
            Sol += E[i].c;
            E[i].use = true;
        }
    }

}

void Print() {
    out << Sol << '\n' << N - 1 << '\n';
    for (int i = 0; i < M; i++)
        if(E[i].use)
            out << E[i].x << " " << E[i].y << '\n';

}

int main() {
    ReadandSort();
    Solve();
    Print();
}