#include<fstream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct much
{
    int cost,a,b;
};
much v[200010];
int tata[400010],adnc[400010],ga,gb,n,m,i,apm[400010],k,s;
bool cmp(much nr1,much nr2)
{
    if(nr1.cost<nr2.cost)
        return 1;
    return 0;
}
int grupa(int x)
{
    int cx=x,y;
    while(x!=tata[x])
        x=tata[x];
    while(cx!=x)
    {
        y=tata[cx];
        tata[cx]=x;
        cx=y;
    }
    return x;
}
void unire(int x,int y)
{
    if(adnc[x]<adnc[y])
        tata[x]=y;
    else
        tata[y]=x;
    if(adnc[x]==adnc[y])
        adnc[x]++;
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
        tata[i]=i;
    for(i=1;i<=m;i++)
    {
        f>>v[i].a>>v[i].b>>v[i].cost;
    }
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=m&&k<n;i++)
    {
        ga=grupa(v[i].a);
        gb=grupa(v[i].b);
        if(ga!=gb)
        {
            s+=v[i].cost;
            apm[++k]=i;
            unire(ga,gb);
        }
    }
    g<<s<<'\n';
    g<<n-1<<'\n';
    for(i=1;i<n;i++)
    {
        g<<v[apm[i]].a<<" "<<v[apm[i]].b<<'\n';
    }
    return 0;
}