#include <bits/stdc++.h>

using namespace std;

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

int n,m,k,arb[200001];
long long c;

struct muchie{
    int x,y,cost;
} v[400001],a[200001];

bool cmp(muchie x,muchie y){
    return x.cost<y.cost;
}

int gas_rad(int node){
    if (arb[node]==node)
        return node;
    return arb[node]=gas_rad(arb[node]);
}

void kruskal(){
    int rad_x, rad_y;
    for (int i=1;i<=n;i++)
        arb[i]=i;

    for (int i=1;i<=m && k<n-1;i++){
        rad_x=gas_rad(v[i].x);
        rad_y=gas_rad(v[i].y);

        if (rad_x!=rad_y) {
            c=c+v[i].cost;
            a[++k]=v[i];
            arb[rad_x]=rad_y;}
        }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].cost;
    sort(v+1,v+m+1,cmp);
    kruskal();
    g<<c<<"\n"<<k<<"\n";
    for(int i=1;i<=k;i++)
        g<<a[i].y<<" "<<a[i].x<<"\n";
    f.close();
    g.close();

    return 0;
}