#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
typedef struct
{
    int x, y, cost;
}MUCHIE;
MUCHIE v[200001],apm[200001];
MUCHIE w;
int n, m, d[200001], s, nr;
int cmp(MUCHIE a, MUCHIE b)
{
    return a.cost<b.cost;
}
void citire()
{
    int i, j, x,y,pret;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>pret;
        w.x=x;
        w.y=y;
        w.cost=pret;
        v[i]=w;
    }
    sort(v+1,v+m+1,cmp);
}
int main()
{
    int i, j, nry;
    citire();
    for(i=1;i<=n;i++)d[i]=i;
    for(i=1;i<=m;i++)
    {
        if(d[v[i].x]!=d[v[i].y])
        {
            s+=v[i].cost;
            apm[++nr].x=v[i].x;
            apm[nr].y=v[i].y;
            nry=d[v[i].y];
            for(j=1;j<=n;j++)if(d[j]==nry)d[j]=d[v[i].x];
        }
    }
    g<<s<<'\n'<<nr<<'\n';
    for(i=1;i<=nr;i++)g<<apm[i].x<<" "<<apm[i].y<<'\n';
    f.close();
    g.close();
    return 0;
}