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

using namespace std;

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

#define MMAX 400000
#define NMAX 200000

int parent[NMAX + 1];

struct ura{
    int x, y, val;
}v[MMAX + 1];

bool cmp(ura a, ura b){
    return a.val < b.val;
}

void initParent(int N){
    for (int i = 1; i <= N; i++){
        parent[i] = i;
    }
}

int findParent(int node){
    if (parent[node] == node){
        return node;
    }
    return parent[node] = findParent(parent[node]);
}

void join(int a, int b){
    parent[findParent(b)] = findParent(a);
}

vector <pair<int, int>> rez;

int main()
{
    int N, M;
    fin >> N >> M;
    for (int i = 1; i <= M; i++){
        int x, y, val;
        fin >> x >> y >> val;
        v[i].x = x;
        v[i].y = y;
        v[i].val = val;
    }
    sort(v + 1, v + M + 1, cmp);
    initParent(N);
    long long cost = 0;
    for (int i = 1; i <= M; i++){
        int a = v[i].x;
        int b = v[i].y;
        if (findParent(a) == findParent(b)){
            continue;
        }
        join(a, b);
        cost += v[i].val;
        rez.push_back({a, b});
    }
    fout << cost << '\n' << rez.size() << '\n';
    for (int i = 0; i < rez.size(); i++){
        fout << rez[i].first << " " << rez[i].second << '\n';
    }
    return 0;
}