#include <iostream>
#include <fstream>
#include <vector>

#define V first
#define C second
#define Infinit 2000000005

using namespace std;

vector < pair <int, int> > G[200005];
int N, P[200005], T[200005], H[200005], NH, Pos[200005];

void Read ()
{
    ifstream fin ("apm.in");
    int i, M, X, Y, c;
    fin >> N >> M;
    for (; M>0; --M)
    {
        fin >> X >> Y >> c;
        G[X].push_back (make_pair (Y, c));
		G[Y].push_back (make_pair (X, c));
    }
    for (i=1; i<=N; ++i)
    {
        P[i]=Infinit;
		H[++NH]=i;
		Pos[i]=NH;
    }
    P[1]=0;
    fin.close ();
}

void Type ()
{
    ofstream fout ("apm.out");
    int i, S=0;
	for (i=1; i<=N; ++i)
	{
		S+=P[i];
	}
	fout << S << "\n" << N-1 << "\n";
    for (i=2; i<=N; ++i)
    {
        fout << i << " " << T[i] << "\n";
		
    }
    fout.close ();
}

inline void Swap (int X, int Y)
{
	int Aux;
	Aux=Pos[H[X]];
	Pos[H[X]]=Pos[H[Y]];
	Pos[H[Y]]=Aux;
	Aux=H[X];
	H[X]=H[Y];
	H[Y]=Aux;
}

void Percolate (int X)
{
    int F=X/2;
    while (F>0)
    {
        if (P[H[F]]<P[H[X]])
        {
            return;
        }
        Swap (X, F);
        X=F;
		F=X/2;
    }
}

void Sift (int X)
{
	int S=2*X;
	while (S<=NH)
	{
		if ((S+1<=NH)&&(P[H[S+1]]<P[H[S]]))
		{
			S++;
		}
		if (P[H[S]]<P[H[X]])
		{
			Swap (X, S);
			X=S;
			S=2*X;
		}
		else
		{
			return;
		}
	}
}

inline void Delete (int X)
{
	Swap (X, NH);
	Pos[H[NH]]=0;
	H[NH]=0;
	NH--;
	Sift (X);
}

void Prim ()
{
    int i, Nod, v, c;
    while (NH>0)
    {
        Nod=H[1];
        Delete (1);
        for (i=0; i<G[Nod].size (); ++i)
        {
            v=G[Nod][i].V;
            c=G[Nod][i].C;
            if ((P[v]>c)&&(Pos[v]!=0))
            {
                P[v]=c;
                T[v]=Nod;
				Percolate (Pos[v]);
            }
        }
    }
}

int main()
{
    Read ();
    Prim ();
    Type ();
    return 0;
}