#include <bits/stdc++.h>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m;
int tat[200005];
int rang[200005];
int sum;
pair < int , int > edges[400005];
int aa=0;

struct edge{
    int n1;
    int n2;
    int cost;
}v[400005];

bool compare(edge a, edge b) {
    return a.cost < b.cost;
}

int find_nod(int nod) {
    while (tat[nod] != nod) {
        nod = tat[nod];
    }
    return nod;
}

void unite_arbs(int x, int y) {
    if (rang[x] < rang[y]) {
        tat[x] = y;
    }
    else if (rang[y] < rang[x]) {
        tat[y] = x;
    }
    else {
        tat[x] = y;
        rang[y]++;
    }
}

int main()
{
    f >> n >> m;
    for (int i=1;i<=m;i++) {
        f >> v[i].n1 >> v[i].n2 >> v[i].cost;
    }
    sort(v+1,v+m+1,compare);

    for (int i=1;i<=n;i++) {
        tat[i] = i;
        rang[i] = 1;
    }

    for (int i=1;i<=m;i++) {
        int x = find_nod(v[i].n1);
        int y = find_nod(v[i].n2);
        if (x != y) {
            unite_arbs(x,y);
            aa++;
            edges[aa].first = v[i].n1; edges[aa].second = v[i].n2;
            sum += v[i].cost;
        }
    }

    g << sum << '\n' << n-1 << '\n';
    for (int i=1;i<=n-1;i++) {
        g << edges[i].first << " " << edges[i].second << '\n';
    }
    return 0;
}