#include <fstream>
#include <vector>
#define NMax 200005
#define oo 10000
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int N,M,NHeap,Cost;
int D[NMax],TT[NMax],S[NMax],Poz[NMax],Heap[NMax];
vector<pair <int, int> > G[NMax], Sol;

void Read()
{
    fin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
        G[y].push_back(make_pair(x,c));

    }
}


void Swap(int X, int Y)
{
    swap(Heap[X],Heap[Y]);
    swap(Poz[Heap[X]],Poz[Heap[Y]]);
}
void Sift(int X)
{
    int Son=(X<<1);
    if(Son+1<=NHeap && D[Heap[Son+1]]<D[Heap[Son]])
      Son++;
    if(Son<=NHeap && D[Heap[Son]]<D[Heap[X]])
        {
            Swap(Son,X);
            Sift(Son);
        }
}
void Percolate(int X)
{
    int F=X>>1;
    if(F && D[Heap[X]]<D[Heap[F]])
        {
            Swap(X,F);
            Percolate(F);
        }
}


void Prim()
{
    for(int i=2;i<=N;i++)
        D[i] = oo;

    for(int i=1;i<=N;i++)
    {
        Poz[i] = i;
        Heap[i] = i;
    }

    NHeap = N;

    for(int i=1;i<=N;i++)
    {
        int Nod = Heap[1];

        Swap(1,NHeap);
        NHeap--;
        Sift(1);

        S[Nod] = 1;

        Cost+=D[Nod];

        if(TT[Nod])
            Sol.push_back(make_pair(TT[Nod],Nod));


        for(unsigned int j = 0; j<G[Nod].size();j++)
        {
            int Vecin = G[Nod][j].first,Cost=G[Nod][j].second;
            if(D[Vecin]>Cost)
            {
                D[Vecin] = Cost;
                if(!S[Vecin])
                    Percolate(Poz[Vecin]);
                TT[Vecin] = Nod;
            }
        }


    }

}

void Print()
{
    fout<<Cost<<"\n";
    fout<<N-1<<"\n";

    for(unsigned int i = 0; i<Sol.size(); i++)
    {
        fout<<Sol[i].first<<" "<<Sol[i].second<<"\n";
    }

}

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