#include <bits/stdc++.h>
#define NMAX 200001
#define MMAX 400001
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int T[MMAX],RANG[NMAX],n,m;
int rad (int x)
{
    if (T[x]==x)
        return x;
   else { T[x]=rad(T[x]);
    return T[x];
   }
}

void unire(int x, int y)
{
    if(rad(x)!=rad(y))
    {
        if(RANG[x]>RANG[y])
        T[y]=x;
        else T[x]=y;
        if(RANG[x]==RANG[y])
            RANG[y]++;
    }
}
struct muchii
{
    int n1,n2,cost;

}v[MMAX],aux;
bool cmp(muchii x, muchii y)
{
    return (x.cost<y.cost);
}
bool verif(int x, int y)
{
    return (rad(x)==rad(y));
}
int main()
{   int ctotal=0,nr=0;
    fin>>n>>m;
    for(int i=1; i<=n; ++i)
        {T[i]=i;}
    bool selectat[NMAX];
    for(int i=1; i<=m; ++i)
    {
        fin>>v[i].n1>>v[i].n2>>v[i].cost;
    }
    sort(v+1,v+m+1,cmp);

    for(int i=1; i<=m; ++i)
        if(!verif(v[i].n2,v[i].n1))
    {
        ctotal+=v[i].cost;
        selectat[i]=true;
        unire(rad(v[i].n1),rad(v[i].n2));
        nr++;
    }
    fout<<ctotal<<"\n"<<n-1<<"\n";
    for(int i=1; i<=m; ++i)
        if(selectat[i]==true) fout<<v[i].n1<<" "<<v[i].n2<<"\n";
    return 0;
}