#include<fstream>
#include<algorithm>
using namespace std;
struct x3
{
    int a;
    int b;
    int cost;
} x[400003];
int t[200003], n, m, i, ra, rb, soll, nr;
pair <int, int> sol[200003];
int rad (int x)
{
    while(t[x]>0)
        x=t[x];
    return x;
}
int cmp (x3 a, x3 b)
{
    return a.cost<b.cost;
}
ifstream in("apm.in");
ofstream out("apm.out");
int main()
{
    in>>n>>m;
    for(i=1; i<=n; i++)
        t[i]=-1;
    for(i=1; i<=m; i++)
        in>>x[i].a>>x[i].b>>x[i].cost;
    sort(x+1, x+m+1, cmp);
    for(i=1; i<=m; i++)
    {
        ra=rad(x[i].a);
        rb=rad(x[i].b);
        if(ra==rb)
            continue;
        soll+=x[i].cost;
        sol[++nr].first=x[i].a;
        sol[nr].second=x[i].b;
        if(t[ra]<t[rb])
        {
            t[ra]+=t[rb];
            t[rb]=ra;
        }
        else
        {
            t[rb]+=t[ra];
            t[ra]=rb;
        }
    }
    out<<soll<<"\n";
    out<<nr<<"\n";
    for(i=1; i<=nr; i++)
        out<<sol[i].first<<" "<<sol[i].second<<"\n";
}