#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int sef[200002];

struct muchie
{
    int x,y,c;
}v[400002];

vector <muchie> rasp;

bool cmp(muchie a, muchie b)
{
    if(a.c>=b.c)
        return false;
    return true;
}

int sefsup(int nod)
{
    if(sef[nod]==nod)
        return nod;
    else
        return sef[nod]=sefsup(sef[nod]);
}

void unire(int nod1, int nod2)
{
    int sefs1=sefsup(nod1),sefs2=sefsup(nod2);
    sef[sefs2]=sefs1;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m,i,nrmuchii,costtotal=0;
    cin>>n>>m;
    nrmuchii=n-1;
    for(i=1;i<=m;i++)
        cin>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=n;i++)
        sef[i]=i;
    for(i=1;i<=m && rasp.size()<nrmuchii;i++)
        if(sefsup(v[i].x)!=sefsup(v[i].y))
        {
            unire(v[i].x,v[i].y);
            rasp.push_back(v[i]);
            costtotal+=v[i].c;
        }
    cout<<costtotal<<'\n'<<nrmuchii<<'\n';
    vector <muchie> :: iterator it;
    for(it=rasp.begin();it<rasp.end();it++)
        cout << (*it).y <<' '<< (*it).x << '\n';
    return 0;
}