#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 Radacina(int x)
{
    if(T[x]==x) return x;
    else
    {
        T[x]=Radacina(T[x]);
        return T[x];
    }
}
void unire(int x, int 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 (Radacina(x)==Radacina(y));
}
int main()
{   int ctotal=0,nr=0;
    fin>>n>>m;
    for(int i=1; i<=n; ++i)
    {
        T[i]=i;
        RANG[i]=0;
    }
    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&&nr<n-1; ++i)
        if(!verif(v[i].n2,v[i].n1))
    {
        ctotal+=v[i].cost;
        selectat[i]=true;
        unire(v[i].n1,v[i].n2);
        nr++;
    }
    fout<<ctotal<<"\n"<<n-1<<"\n";
    for(int i=1; i<=m; ++i)
        if(selectat[i]==true) fout<<v[i].n2<<" "<<v[i].n1<<"\n";
    return 0;
}