#include <bits/stdc++.h>
#include <queue>
#include <functional>
#define NMAX 200001
#define MMAX 400001

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie {
    int x, y, cost;
    friend bool operator > (muchie, muchie);
};

bool operator > (muchie A, muchie B) {
    return A.cost > B.cost;
}

int n, m, costArbore, nr;
int tata[NMAX], h[NMAX];
priority_queue<muchie, vector<muchie>, greater<muchie> > H;
vector<muchie> V;

int Find(int x) {
    int rad = x, y;
    while(tata[rad]) rad = tata[rad];

    //compresia drumului
    if(rad != x) {
        y = tata[x];
        while(y != rad) {
            tata[x] = rad;
            x = y;
            y = tata[x];
        }
    }
    return rad;
}

void Union(int x, int y) {
    int i = Find(x);
    int j = Find(y);
    if(i != j) {
        if(h[i] < h[j])
            tata[i] = j;
        else if(h[j] < h[i])
            tata[j] = i;
        else {
            tata[i] = j;
            h[j]++;
        }
    }
}

void citire() {
    fin >> n >> m;
    int a, b, c;
    muchie aux;
    for(int i = 0; i < m; i++) {
        fin >> a >> b >> c;
        aux.x = a, aux.y = b, aux.cost = c;
        H.push(aux);
    }
}

void Krushkal() {
    int i, j;
    muchie aux;
    while(V.size() < n - 1) {
        aux = H.top();
        H.pop();
        i = Find(aux.x);
        j = Find(aux.y);
        if(i != j) {
            V.push_back(aux);
            costArbore += aux.cost;
            Union(i, j);
        }
    }
}

void afisare() {
    fout << costArbore << '\n';
    fout << V.size() << '\n';
    for(int i = 0; i < V.size(); i++) {
        fout << V[i].x << ' ' << V[i].y << '\n';
    }
}

int main()
{
    citire();
    Krushkal();
    afisare();
    return 0;
}