#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int L[200001],m,n,COST,m1;
struct muchie
{
    int x,y,cost;
} u[400001];
void initializare()
{
    for(int i=1; i<=n; i++)
        L[i]=i;
}
void ordonare()
{
    for(int i=1; i<m; i++)
        for(int j=i+1; j<=m; j++)
            if(u[i].cost>u[j].cost)
                swap(u[i],u[j]);
}
int main()
{
    /**Algoritmul lui Kruskal pentru determinarea arborelui partial de cost
    minim (APM) dintr-un graf neorientat.*/
    ///APM are exact n-1 muchii din graf, deoarece este un arbore.
    int n;
    f>>n>>m1;
    int x,y,cost;
    while(f>>x>>y>>cost)
    {
        m++;
        u[m].x=x;
        u[m].y=y;
        u[m].cost=cost;
    }
    ///initializare();
    for(int i=1; i<=n; i++)
        L[i]=i;
    ordonare();///ordonez muchiile crescator dupa cost
    int nr=0,i=1;///pornesc de la prima muchie
    do
    {
        int x=u[i].x,y=u[i].y;
        if(L[x]!=L[y])
        {
            nr++;///cresc numarul de muchii selectate
            //g<<x<<" "<<y<<endl;
            COST+=u[i].cost;///actualizez costul
            int a=L[x],b=L[y];
            /**reunesc subarborii = toate elem subarborelui b
            se 'lipesc' la arborele a*/
            for(int j=1; j<=n; j++)
                if(L[j]==b)
                    L[j]=a;
        }
        i++;///trec la urmatoarea muchie
    }
    while(nr<n-1&&i<m);
    g<<COST<<endl<<nr<<endl;;
    for(int i=1;i<=nr;i++)
        g<<u[i].x<<" "<<u[i].y<<endl;
    return 0;
}