#include <fstream>
#include <algorithm>
#define Nmax 200001
#define Mmax 400001
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

int n, m, tata[Nmax], rang[Nmax], total;
struct muchii {
    int x, y, c;
} v[Mmax];
pair <int, int> rez[Nmax];

bool comp(muchii a, muchii b) {
    return a.c < b.c;
}

int find(int nod) {
    while (tata[nod]!=nod)
        nod= tata[nod];
    return nod;
}

void unire(int x, int y) {
    if (rang[x] < rang[y])
        tata[x]= y;
    else if (rang[x] > rang[y])
        tata[y]= x;
    else
    {
        tata[x]= y;
        rang[y]++;
    }
}

int main() {
    cin>>n>>m;
    for (int i=1; i<=m; i++)
        cin>> v[i].x >> v[i].y >> v[i].c;
    sort(v+1, v+m+1, comp);

    for (int i=1; i<=n; i++)
        tata[i]= i, rang[i]= 1;

    int k= 0;
    for (int i=1; i<=m; i++)
    {
        int x= find(v[i].x);
        int y= find(v[i].y);
        if (x != y)
        {
            unire(x, y);
            rez[++k].first= v[i].x;
            rez[k].second= v[i].y;
            total+= v[i].c;
        }
    }
    cout<< total <<"\n"<< n-1 <<"\n";
    for (int i=1; i<n; i++)
        cout<< rez[i].first <<" "<< rez[i].second <<"\n";
    return 0;
}