#include <stdio.h>
#include <vector>
using namespace std;
#define IN "apm.in"
#define OUT "apm.out"
#define NMAX 200005
#define MMAX 400005
#define mp make_pair
#define pb push_back

struct MUCHIE {int x; int y; int cost;};
MUCHIE heap[MMAX],a;
vector< pair<int,int> > sol;
int n,m,heap_nodes,CTOTAL;
int parinte[NMAX],inaltime[NMAX];

void citire();
void kruskal();
void afisare();
void inserare(MUCHIE H[], int &n, MUCHIE x);
void extrageMIN(MUCHIE H[], int &n);
void combinare(MUCHIE H[], int &n, int i);
int FIND(int x);
void UNION(int x, int y);

int main()
{
    citire();
    kruskal();
    afisare();

    return 0;
}

void citire()
{
    FILE * fin=fopen(IN,"r");

    int i;
    fscanf(fin,"%d%d",&n,&m);
    fscanf(fin,"%d%d%d",&heap[1].x,&heap[1].y,&heap[1].cost); heap_nodes=1;
    for(i=2;i<=m;i++)
    {
        fscanf(fin,"%d%d%d",&a.x,&a.y,&a.cost);
        inserare(heap,heap_nodes,a);
    }

    fclose(fin);
}

void kruskal()
{
    int contor,comp1,comp2;
    for(contor=1;contor<=n-1; )
    {
        extrageMIN(heap,heap_nodes);
        comp1=FIND(a.x);
        comp2=FIND(a.y);
        if(comp1!=comp2)
        {
            contor++;
            UNION(a.x,a.y);
            CTOTAL+=a.cost;
            sol.pb(mp(a.x,a.y));
        }
    }
}

void inserare(MUCHIE H[], int &n, MUCHIE x)
{
    int fiu,tata;
    n++;
    fiu=n; tata=n/2;
    //restaurez proprietatea de heap
    while(tata>0 && H[tata].cost>x.cost)
    {
        H[fiu]=H[tata];
        fiu=tata;
        tata=tata/2;
    }
    //pun pe x
    H[fiu]=x;
}

void extrageMIN(MUCHIE H[], int &n)
{
    a=H[1];
    H[1]=H[n];
    n--;
    combinare(H,n,1);
}

void combinare(MUCHIE H[], int &n, int i)
{
    MUCHIE x=H[i];
    int tata=i;
    int fiu=2*i;
    while(fiu<=n)
    {
        if(fiu+1<=n && H[fiu+1].cost<H[fiu].cost) fiu++;
        if(x.cost<H[fiu].cost) break;
        //nu e in regula
        H[tata]=H[fiu];
        tata=fiu;
        fiu=2*tata;
    }
    H[tata]=x;
}

int FIND(int x)
{
	int rad=x,aux;
	while(parinte[rad]!=0)
            rad=parinte[rad];
	while(parinte[x]!=0)
	{
		aux=parinte[x];
		parinte[x]=rad;
		x=aux;
	}
	return rad;
}

void UNION(int x, int y)
{
	if(inaltime[x]<inaltime[y])
        parinte[x]=y;
    else
    {
        if(inaltime[y]<inaltime[x])
            parinte[y]=x;
	    else
	    {
                parinte[x]=y;
                inaltime[y]++;
        }
    }
}

void afisare()
{
    FILE * fout=fopen(OUT,"w");

    int i;
    fprintf(fout,"%d\n%d\n",CTOTAL,sol.size());
    for(i=0;i<sol.size();i++)
        fprintf(fout,"%d %d\n",sol[i].first,sol[i].second);

    fclose(fout);
}