#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct muchie
{
    int x,y,cost;
};
struct sol
{
    int m1,m2;
};
muchie v[400005];
sol a[400005];
int tata[200005],n,m,niv[200005],nr,t1,t2,sum;
bool cmp(muchie a, muchie b)
{
    return a.cost<b.cost;
}
int find (int x)
{
    int a=x,r=x;
    while (tata[r])
        r=tata[r];
    while (tata[a])
    {
        int z=tata[a];
        tata[a]=r;
        a=z;
    }
    return r;
}
void unite (int a,int b)
{
    if (a!=b)
    {
        if (niv[a]<niv[b])
            tata[a]=b;
        else if (niv[b]<niv[a])
            tata[b]=a;
        else
        {
            tata[b]=a;
            niv[a]++;
        }
    }
}

int main()
{
    in>>n>>m;
    for (int i=1; i<=m; i++)
        in>>v[i].x>>v[i].y>>v[i].cost;
    sort (v+1,v+m+1,cmp);
    for (int i=1; i<=m&&nr<n-1; i++)
    {
        t1=find(v[i].x);
        t2=find(v[i].y);
        if (t1!=t2)
        {
            nr++;
            sum+=v[i].cost;
            a[nr].m1=v[i].x;
            a[nr].m2=v[i].y;
            unite(t1,t2);
        }
    }
    out<<sum<<'\n';
    out<<nr<<'\n';
    for (int i=1; i<=nr; i++)
        out<<a[i].m1<<" "<<a[i].m2<<'\n';
    return 0;
}