#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,i,m,h[200010],parent[200010],cost,sz;

struct muchii
{
    int a,b,cost;
} v[400010],sol[200010];

int compare(muchii x,muchii y)
{
    return x.cost<y.cost;
}

int parent_of(int n)
{
    if (parent[n]!=n) return parent_of(parent[n]);
    return n;
}

int muchie (int r1,int r2)
{
    r1=parent_of(r1);
    r2=parent_of(r2);
    if (r1==r2) return 0;
    else
    {
        if (h[r1]<h[r2]) parent[r1]=r2;
        else if (h[r2]<h[r1]) parent[r2]=r1;
        else {parent[r2]=r1; h[r1]++; }
    }
    return 1;
}

void kruskall()
{
    int k=1,muchii=0,r1,r2;

    while (muchii<n-1)
    {
        r1=v[k].a;
        r2=v[k].b;
        if (muchie(r1,r2)) {muchii++; cost+=v[k].cost;
        sz++; sol[sz].a=r1; sol[sz].b=r2;}
        k++;
    }

}

int main()
{
    f>>n>>m;
    for (i=1; i<=m; i++)
        f>>v[i].a>>v[i].b>>v[i].cost;

    for (i=1; i<=n; i++)
    {
        h[i]=1;
        parent[i]=i;
    }

    sort (v+1,v+m+1,compare);

    kruskall();

    g<<cost<<'\n';
    g<<sz<<'\n';
    for (i=1;i<=sz;i++)
        g<<sol[i].a<<" "<<sol[i].b<<'\n';

    return 0;
}