#include<fstream>
#include<algorithm>
using namespace std;
ifstream A("apm.in");
ofstream B("apm.out");
#define N 200001
int d[N],x[2*N],y[2*N],c[2*N],n,m,e,p[2*N],l[N],i,j;
int E(int x)
{
    if(d[x]==x)
        return x;
    d[x]=E(d[x]);
    return d[x];
}
void R(int x,int y)
{
    d[E(x)]=E(y);
}
bool F(int a,int b)
{
    return c[a]<c[b];
}
int main()
{
    A>>n>>m;
    for(i=0;i<m;++i)
        A>>x[i]>>y[i]>>c[i],d[i]=p[i]=i;
    sort(p,p+m,F);
    for(i=0;i<m;++i)
        if(E(x[p[i]])!=E(y[p[i]]))
            e+=c[p[i]],R(x[p[i]],y[p[i]]),l[j++]=p[i];
    B<<e<<"\n"<<(n-1)<<"\n";
    for(i=0;i<n-1;++i)
        B<<x[l[i]]<<" "<<y[l[i]]<<"\n";
    return 0;
}