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

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

int N,M,Cost;
int D[NMax],TT[NMax],S[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 Prim()
{
    for(int i=2;i<=N;i++)
        D[i] = oo;

    for(int i=1;i<=N;i++)
    {
        int Min = oo,Nod;

        for(int j=1; j<=N; j++)
        {
            if(D[j]<Min && !S[j])
            {
                Min = D[j];
                Nod = j;
            }
        }

        S[Nod] = 1;

        Cost+=Min;

        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;
                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;
}