#include <fstream>
#define edges 400001
#define nodes 200001
#include <algorithm>
using namespace std;


struct muchie
{
    int v1, v2, cost;
};

muchie v[edges];

int dad[nodes], child[nodes], n, m, a, b, c, muchii, found, total, sol[nodes][2];

bool cmp(muchie x, muchie y)
{
    return x.cost<y.cost;
}

int arb(int x)
{
    int start=x;
    while(dad[x]!=x)
    {
        x=dad[x];
    }
    while(dad[start]!=start)
    {
        int tmp=start;
        start=dad[start];
        dad[tmp]=x;
    }
    return x;
}

void unite(int x, int y)
{
    if(child[x]>child[y])
    {
        child[x]+=child[y];
        dad[y]=x;
    }
    else
    {
        child[y]+=child[x];
        dad[x]=y;
    }
}

int main()
{
    ifstream in("apm.in");
    ofstream out ("apm.out");
    in>>n>>m;
    muchii=m;
    while(m>=1)
    {
        in>>a>>b>>c;
        v[m].v1=a; v[m].v2=b; v[m].cost=c;
        m--;
    }
    sort(v+1, v+muchii+1, cmp);
    for(int i=1; i<=n; ++i)
        dad[i]=i, child[i]=1;
    for(int i=1; i<=muchii && found<=n-1; ++i)
    {
        if(arb(v[i].v1)!=arb(v[i].v2))
        {
            total+=v[i].cost;
            unite(dad[v[i].v1], dad[v[i].v2]);
            sol[++found][1]=v[i].v1;
            sol[found][0]=v[i].v2;
        }
    }
    out<<total<<"\n"<<n-1<<"\n";
    for(int i=1; i<n; ++i)
    {
        out<<sol[i][0]<<" "<<sol[i][1]<<"\n";
    }
    in.close();
    out.close();
    return 0;
}