#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int v[2002];
struct muc
{
    int x,y;
    float w;
} l[2002];
int find(int x)
{
    if(v[x]==x)
        return x;
    return find(v[x]);
}
int cmp(muc a,muc b)
{
    return (a.w<b.w);
}
int main()
{
    int n,M,i,mu[2002];
    f>>n>>M;
    //citire
    for(i=0; i<M; i++)
        {f>>l[i].x>>l[i].y>>l[i].w;
        }
    for(i=1; i<=n; i++)
       {v[i]=i;
           mu[i]=1;
       }
    sort(l,l+M,cmp);
    int    k=0;
    muc m,l_fin[2002];
    i=0;
    int s=0;
    int x,y;
    while(k<n-1)
    {
        m=l[i];
        x=m.x;
        y=m.y;
        int     x_p=find(x);
        int     y_p=find(y);
        if(x_p!=y_p)
        {l_fin[k]=l[i];
         s+=l[i].w;
         k++;
            if(mu[x_p]>=mu[y_p]){
                v[y_p]=x;
                mu[x_p]+=mu[y_p];
            }
            else{
                v[x_p]=y;
                mu[y_p]+=mu[x_p];
            }

        }
        i++;
    }
    g<<s<<endl<<k<<endl;
    for(i=0;i<k;i++)
        g<<l_fin[i].x<<" "<<l_fin[i].y<<"\n";

}