#include <bits/stdc++.h>

using namespace std;

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

struct ura {
    int x,y,cost;
} v[400001],rez[400001];

int tata[200001],sol;

bool cmp(ura a,ura b) {
    if(a.cost<b.cost)
        return true;
    else
        return false;
}

int sef(int n){
    if(tata[n]==n)
        return n;
    else
        return tata[n]=sef(tata[n]);
}

void unire(int x,int y)
{
    int sef1,sef2;
    sef1=sef(x);
    sef2=sef(y);
    tata[sef2]=sef1;
}

int main() {
    int n,m,i,j;
    in>>n>>m;
    for(i=1;i<=n;++i)
        tata[i]=i;

    for(i=1; i<=m; ++i)
        in>>v[i].x>>v[i].y>>v[i].cost;
    sort(v+1,v+m+1,cmp);
    int k=0;
    for(i=1;i<=m&&k<n-1;++i)
    {
        if(sef(v[i].x)!=sef(v[i].y))
        {
            sol+=v[i].cost;
            k++;
            rez[k].x=v[i].x;
            rez[k].y=v[i].y;
            unire(v[i].x,v[i].y);
        }

    }
    out<<sol<<'\n'<<n-1<<'\n';
    for(i=1;i<n;++i)
        out<<rez[i].x<<" "<<rez[i].y<<'\n';
    return 0;
}