#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct muchisoare
{
    int x, y, cost;
}v[400005];
int dad[200005];
int rang[200005];
vector <muchisoare> sol;
bool comp (muchisoare a, muchisoare b)
{
    if (a.cost<b.cost) return true;
    return false;
}
int search_dad(int nod)
{
    while (dad[nod]!=0) {
        nod=dad[nod];
    }
    return nod;
}
int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int n, m;
    cin>>n>>m;
    for (int i=0; i<m; i++) {
        cin>>v[i].x>>v[i].y>>v[i].cost;
    }
    sort(v, v+m, comp);
    for (int i=1; i<=n; i++) {
        //dad[i]=i;
        rang[i]=1;
    }
    int S=0;
    for (int i=0; i<m; i++) {
        int x=v[i].x, y=v[i].y;
        int rad1=search_dad(x);
        int rad2=search_dad(y);
        if (rad1==rad2) continue;
        S+=v[i].cost;
        if (rang[rad1]<rang[rad2]) {
            dad[rad1]=rad2;
            rang[rad2]+=rang[rad1];
        }
        else {
            dad[rad2]=rad1;
            rang[rad1]=rang[rad2];
        }
        sol.push_back(v[i]);
    }
    cout<<S<<'\n';
    cout<<n-1<<'\n';
    for (auto muc : sol) {
        cout<<muc.x<<' '<<muc.y<<'\n';
    }
    return 0;
}