#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int x,y,cost,cost_total,k,n,m,i,t[200001],r[200001],sol[800001];
struct muchie
{
    int x,y,cost;
};
muchie v[400001];
bool compara(muchie x,muchie y)
{
    return (x.cost<y.cost);
}
int findset(int x)
{
    while (t[x]!=x)
        x=t[x];
    return x;
}
void union_set(int x,int y)
{
    if (r[x]>r[y])  /// unire arbore mare de arbore mic - test pentru timp
        t[x]=y;
    else if (r[y]>r[x])  /// unire arbore mare de arbore mic - test pentru timp
        t[y]=x;
    else
    {
        r[x]++;
        t[y]=x;
    }
}
int main()
{
    in>>n>>m;
    for (i=1; i<=n; ++i)
    {
        t[i]=i;
        r[i]=1;
    }
    for (i=1; i<=m; ++i)
    {
        in>>x>>y>>cost;
        v[i].x=x;
        v[i].y=y;
        v[i].cost=cost;
    }
    sort(v+1,v+m+1,compara);
    for (i=1; i<=m; ++i)
    {
        int x = findset(v[i].x);
        int y = findset(v[i].y);
        if (x!=y)
        {
            union_set(x,y);
            sol[++k]=v[i].x;
            sol[++k]=v[i].y;
            cost_total+=v[i].cost;
        }
    }
    out<<cost_total<<"\n"<<k/2<<"\n";
    for (i=1; i<=k; i+=2)
        out<<sol[i]<<" "<<sol[i+1]<<"\n";
}