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

using namespace std;

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

struct muchie {
    int x, y, cost;
    int viz=0;
} muc[200001];

int n, m;
int t[200001], h[200001];

void init() {
    for (int i=1; i<=n; i++) {
        t[i]=i;
        h[i]=1;
    }
}

int find(int x) {
    int r=x;
    while (t[x]!=x)
        x=t[x];
    while (r!=x) {
        int next=t[r];
        t[r]=x;
        r=next;
    }
    return x;
}

void unite(int x, int y) {
    int ty=find(y);
    int tx=find(x);
    if (h[ty]<h[tx]) {
        t[ty]=tx;
        h[ty]=h[tx];
    } else if (h[tx]<h[ty]) {
        t[tx]=ty;
        h[tx]=h[ty];
    } else {
        t[tx]=ty;
        h[ty]++;
        h[tx]=h[ty];
    }
}

bool comp(muchie a, muchie b) {
    return a.cost<b.cost;
}

void citire() {
    fin>>n>>m;
    for (int i=0; i<m; i++)
        fin>>muc[i].x>>muc[i].y>>muc[i].cost;
}

int kruskal() {
    int c=0;
    for (int i=0; i<m; i++) {
        if (find(muc[i].x)!=find(muc[i].y)) {
            muc[i].viz=1;
            c+=muc[i].cost;
            unite(muc[i].x, muc[i].y);
        }
    }
    return c;
}

void afisare() {
    fout<<kruskal()<<'\n'<<n-1<<'\n';
    for (int i=0; i<m; i++)
        if (muc[i].viz)
            fout<<muc[i].x<<' '<<muc[i].y<<'\n';
}

int main() {
    citire();
    init();
    sort(muc, muc+m, comp);
    afisare();
    return 0;
}