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

const int NMax = 2e5 + 2;
int N, M, TT[NMax], R[NMax], IdX[NMax], Sol, K;

struct Edgy{
    int x, y, c;
};
Edgy E[NMax];

bool Comp(Edgy x, Edgy y){
    return (x.c < y.c);
}

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

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

void Kruskal(){
    for (int i = 1; i <= N; ++i)
        TT[i] = i;
    sort(E + 1, E + M + 1, Comp);
    for (int i = 1; i <= M; ++i){
        int a = Root(E[i].x), b = Root(E[i].y);
        if (a != b){
            Unite(a, b);
            Sol += E[i].c;
            IdX[++K] = i;
        }
    }
}

void Print(){
    out << Sol << '\n' << N-1 << '\n';
    for (int i = 1; i <= K; ++i)
        out << E[IdX[i]].x << " " << E[IdX[i]].y << '\n';
}

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

int main(){
    Read();
    Kruskal();
    Print();
    return 0;
}