#include <bits/stdc++.h>
#define NMAX 200001
#define MMAX 400001
using namespace std;
typedef long long ll;

int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, 1, -1};

const string file = "apm";

ifstream fin(file + ".in");
ofstream fout(file + ".out");

int n, m, cost, x, y, k_much;
int dad[NMAX], h[NMAX];

struct nod{
    int x, y, cst, idk;
}muchii[MMAX];

bool cmp(nod a, nod b){
    return a.cst < b.cst;
}

int root(int x) {
    while (dad[x] != x)
        x = dad[x];
    return x;
}

void uniune(int x, int y) {
    if (h[x] > h[y])
        dad[y] = x;
    else if (h[x] < h[y])
        dad[x] = y;
    else {
        h[x]++;
        dad[y] = x;
    }
}

void kruskal(){
    for(int i = 1; i <= n; i++)
        dad[i] = i, h[i] = 1;
    sort(muchii + 1, muchii + m + 1, cmp);
    cost = 0; k_much = 0;
    for(int i = 1; i <= m && k_much < n - 1; i++){
        int r1 = root(muchii[i].x);
        int r2 = root(muchii[i].y);
        if(r1 != r2){
            uniune(r1, r2);
            k_much++;
            cost += muchii[i].cst;
            muchii[i].idk = 1;
        }
    }
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        fin >> x >> y >> cost;
        muchii[i].x = x;
        muchii[i].y = y;
        muchii[i].cst = cost;
    }
    kruskal();
    fout << cost << "\n" << n - 1 << "\n";
    for(int i = 1; i <= m; i++)
        if(muchii[i].idk)
            fout << muchii[i].x << " " << muchii[i].y << "\n";
    return 0;
}