#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)
{
    int rx=rad(x);
    int ry=rad(y);
    if (rx!=ry)
        T[ry]=rx;

}

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(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;
}