#include <iostream>
#include <fstream>
#define MAXIM 200002
using namespace std;
ifstream f ("date.in");
ofstream g ("kruskal.out");


int n,i;
struct nod {int x,y;} sol[MAXIM];


struct muchie {
    int x,y,c;
} v[2*MAXIM];

int t[2*MAXIM+1],m,k,cost;

int indvalmin (int i, int n)
{
    if (2*i+1<=n)
        if(v[2*i].c<v[2*i+1].c)
            return 2*i;
        else
            return 2*i+1;
    else
        return 2*i;
}


void combinare (int i, int n)
{
    int ind;
    muchie aux;
    if (i<=n/2)
        {
            ind=indvalmin(i,n);
            if (v[i].c>v[ind].c)
                {
                   swap(v[i],v[ind]);
                    combinare (ind,n);
                }
        }
}

void minheap ()
{
    for (i=n/2;i>=1;i--)
        combinare(i,n);
}



void rezolva()
{   for(int i=1;i<=2*n+1;i++)
      t[v[i].x]=t[v[i].y]=-1;
      t[v[1].x]=1;

    for(int i=1;i<=2*n+1;i++)
    {
        if(t[v[i].x]*t[v[i].y]==-1)
        {  k++;
           cost=cost+v[i].c;
            sol[k].x=v[i].x;
            sol[k].y=v[i].y;
           t[v[i].x]=1;
           t[v[i].y]=1;
        }
    }

}

int main()
{   ifstream f ("apm.in");
    ofstream g ("apm.out");

    f>>n>>m;
    for (int i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].c;

    minheap ();
    rezolva();

    g<<cost<<"\n"<<n-1<<"\n";
    for (int i=1; i<=k; i++)
    g<<sol[i].x<<" "<<sol[i].y<<"\n";
    g.close();
    return 0;
}