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

using namespace std;

class Graf
{
    unsigned long N, M;
    struct muchie {unsigned long x, y; short c;};
    struct semi {unsigned long nod; short cost;};
    long cost;
    //vector <muchie> toate;
    vector <muchie> A;
    vector < semi > G[200000];
public:
    void citire();
    void prim (unsigned long r);
    void afisare ();
    ~Graf();
};

Graf::~Graf()
{
    delete G;
}

void Graf::afisare()
{
    ofstream f ("apm.out");
    f<<cost<<'\n'<<N-1<<'\n';
    unsigned long i;
    for (i=0; i<A.size(); i++)
    {
        f<<A[i].x<<' '<<A[i].y<<'\n';
    }
}

void Graf::prim(unsigned long r)
{
    semi v[N+3]; //first-nodul din arbore de care se leaga nodul i; second-costul
    unsigned long i, j, x, minim;
    short c;
    cost=0;
    muchie m;
    for (i=0; i<=N; i++)
    {
        v[i].cost=2000;
    }
    v[r].cost=-2000;//un nod are costul -2000 daca apartine arborelui
    v[r].nod=0;
    for (i=1; i<N; i++)
    {
        //in r avem ultimul nod ales
        for (j=0; j<G[r].size(); j++)
        {
            x=G[r][j].nod;
            c=G[r][j].cost;
            if (c<v[x].cost && c!=-2000)
            {
                v[x].cost=c;
                v[x].nod=r;
            }
        }
        //am updatat vectorul
        minim=0;
        for (j=1; j<=N; j++)
        {
            if (v[j].cost<v[minim].cost && v[j].cost!=-2000)
            {
                minim=j;
            }
        }
        m.x=minim;
        m.y=v[minim].nod;
        m.c=v[minim].cost;
        A.push_back(m);
        cost+=m.c;
        v[minim].cost=-2000;
        r=minim;
    }
}

void Graf::citire()
{
    ifstream f ("apm.in");
    f>>N>>M;
    //muchie m;
    unsigned long i, x, y;
    short c;
    semi s;
    //G=new vector< semi > [N+3];
    for(i=0; i<M; i++)
    {
        //f>>m.x>>m.y>>m.c;
        f>>x>>y>>c;
        //toate.push_back(m);
        s.cost=c;
        s.nod=y;
        G[x].push_back(s);
        s.nod=x;
        G[y].push_back(s);
        //cout<<m.x<<' '<<G[m.x][G[m.x].size()-1].first<<' '<<G[m.x][G[m.x].size()-1].second<<'\n';
    }
}

int main()
{
    Graf G;
    G.citire();
    G.prim(1);
    G.afisare();
    return 0;
}