// determinarea unui arbore partial de cost minim cu algoritmul lui Prim
#include<fstream>
#include<algorithm>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{
    int x,y,c;
};
muchie u[400001],aux;
int m=0,n,i,j,k,a,b,nr,viz[200001],cost,L[200001],m1;

bool cmp(muchie a, muchie b)
{
    return a.c<b.c;
}
int main()
{
    f>>n>>m1;
    while (f>>i>>j>>k)
    {
        m++;
        u[m].x=i;
        u[m].y=j;
        u[m].c=k;
    }

//Ordonarea muchiilor dupa cost
    sort(u+1,u+m+1,cmp);
    /*for(i=1; i<m; i++)
        for(j=i+1; j<=m; j++)
            if (u[i].c>u[j].c)
            {
                aux=u[i];
                u[i]=u[j];
                u[j]=aux;
            }
*/
//Initializari
    cost=u[1].c;
    L[1]=1;
    viz[u[1].x]=viz[u[1].y]=1;

//Algoritmul lui Prim
    for(i=2; i<=n-1; i++) //am gasit un arbore cand am ales n-1 muchii
        for(int j=2; j<=m; j++) //j cauta muchii
            if (viz[u[j].x]!=viz[u[j].y])
            {
                cost+=u[j].c;
                viz[u[j].x]=viz[u[j].y]=1;
                L[i]=j;
                break;
            }

    g<<cost<<'\n'<<n-1<<'\n';
    for(i=1; i<n; i++) g<<u[L[i]].x<<' '<<u[L[i]].y<<'\n';
}