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

using namespace std;

#define Nmax 400002

struct edge{

    int x;
    int y;
    int cost;

} muchie[Nmax];

int padure[Nmax];
vector < pair <int,int> > lista(Nmax);

int N, M, cost;

void citire(){

    ifstream f("apm.in");

    f >> N >> M;

    for(int i = 1; i <= M; i++)
        f >> muchie[i].x >> muchie[i].y >> muchie[i].cost;

    f.close();
}

int cmp(edge a, edge b){

    return a.cost < b.cost;
}

void init(){

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

void Kruskal(){

    int k = 1, i = 1, l = 1;

    while(k < N){

        if(padure[muchie[i].x] != padure[muchie[i].y]){

            k++;

            lista[l].first = muchie[i].x;
            lista[l++].second = muchie[i].y;

            cost += muchie[i].cost;

            int v = padure[muchie[i].x], w = padure[muchie[i].y];

            for(int j = 1; j <= N; j++)
                if(padure[j] == v)
                    padure[j] = w;
        }

        i++;
    }
}

void afis(){

    ofstream g("apm.out");

    g << cost << "\n";
    g << N-1 << "\n";

    for(int i = 1; i < N; i++)
        g << lista[i].first << " " << lista[i].second << "\n";


    g.close();
}

int main(){

    citire();
    init();
    sort(muchie + 1, muchie + 1 + M, cmp);
    Kruskal();
    afis();

    return 0;
}