#include <fstream>
#include <iostream>
#include <algorithm>
#define NMaxVf 50
#define NMaxMuchii NMaxVf*(NMaxVf*1)/2
using namespace std;
struct Muchie
{
    int e1, e2, cost;
};
Muchie G[NMaxMuchii];
int A[NMaxVf], c[NMaxVf];///A memoreaza arborele partial de cost minim
///c retine evidenta componentelor conexe
int n, m;
bool sortare(Muchie x, Muchie y)
{
    if (x.cost<y.cost)
     return 1;
     return 0;
 }
void initializare()
{
    int i;
    ifstream f("apm.in");
    f>>n>>m;
    for(i=1; i<=m; i++)
        f>>G[i].e1>>G[i].e2>>G[i].cost;
         sort(G+1,G+m+1,sortare);
    for (i=1; i<=n; i++) c[i]=i;
}

void  afisare()
{
    int i, cost_APM=0, nr=0;
    ofstream f("apm.out");
    for (i=1; i<n; i++)
    {
        cost_APM+=G[A[i]].cost;
        nr++;
        }
       f <<cost_APM;
       f <<'\n'<<nr<<'\n';
       for (i=1; i<n; i++)
        f<<G[A[i]].e1<<' '<<G[A[i]].e2<<'\n';
}
int main()
{
    int i, j, minim,maxim, NrMSel;
    initializare();
    NrMSel=0;
    for(i=1; NrMSel<n-1; i++)
        if (c[G[i].e1]!=c[G[i].e2])
        { A[++NrMSel]=i;
    if (c[G[i].e1]<c[G[i].e2])
    {
        minim=c[G[i].e1];
        maxim=c[G[i].e2];
    }
    else
    {
        minim=c[G[i].e2];
        maxim=c[G[i].e1];
    }
    for(j=1; j<=n; j++)
        if(c[j]==maxim) c[j]=minim;
        }
afisare();

    return 0;
}