#include <iostream>
#include<fstream>
#include<utility>
#include<algorithm>
using namespace std;
int *r,n;
struct muchie
{
    int u,v,w;
};
void sortare_q(muchie *a,int s,int d)
{
    int i,j,aux,m;
    i = s ;
    j = d ;
    m = a[(s+d)/2].w;
    while( i <= j )
    {
        while( m > a[i].w )
            i++;
        while( m < a[j].w )
            j--;
        if( i <= j)
        {
            aux=a[i].w;
            a[i].w=a[j].w;
            a[j].w=aux;
            aux=a[i].v;
            a[i].v=a[j].v;
            a[j].v=aux;
            aux=a[i].u;
            a[i].u=a[j].u;
            a[j].u=aux;
            i++;
            j--;
        }
    }
    if(s<j)
        sortare_q(a,s,j);
    if(d>i)
        sortare_q(a,i,d);

}
void initializare(int u)
{
    r[u]=u;
}
int componenta(int u)
{
    return r[u];
}
void reuneste(int u,int v)
{
    int cu,cv,i;
    cu=r[u];
    cv=r[v];
    for(i=0;i<n;i++)
        if(r[i]==r[u])
            r[i]=r[v];
    r[u]=r[v];
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int nrm,i,k,j,cost=0;
    muchie *m;
    pair <int,int> *arb;
    arb=new pair<int,int> [n];
    f>>n>>nrm;
    m=new muchie [nrm+1];
    r=new int [n];
    for(i=0;i<nrm;i++)
        f>>m[i].u>>m[i].v>>m[i].w;
    sortare_q(m,0,nrm-1);
    for(i=0;i<n;i++)
        initializare(i);
    k=0;
    for(i=0;i<nrm;i++)
    {
        if(componenta(m[i].u)!=componenta(m[i].v))
        {
            arb[k].first=m[i].u;
            arb[k].second=m[i].v;
            cost+=m[i].w;
            k++;
            reuneste(m[i].u,m[i].v);
            if(k==n-1)
            {
                g<<cost<<endl;
                g<<k<<endl;
                for(j=0;j<k;j++)
                    g<<arb[j].first<<" "<<arb[j].second<<endl;
                return 0;
            }
        }
    }

    return 0;
}