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

using namespace std;

class Graf
{
    unsigned long N, M;
    struct muchie {unsigned long x, y; short c;};
    long cost;
    vector <muchie> toate;
    vector <muchie> A;
    vector < pair <unsigned long, short> > *G;
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<N-1; i++)
    {
        f<<A[i].x<<' '<<A[i].y<<'\n';
    }
}

void Graf::prim(unsigned long r)
{
    pair <unsigned long, short> v[N+1]; //first-nodul din arflore 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].second=2000;
    }
    v[r].second=-2000;//un nod are costul -2000 daca apartine arborelui
    v[r].first=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].first;
            c=G[r][j].second;
            if (c<v[x].second && c!=-2000)
            {
                v[x].second=c;
                v[x].first=r;
            }
        }
        //am updatat vectorul
        minim=0;
        for (j=1; j<=N; j++)
        {
            if (v[j].second<v[minim].second && v[j].second!=-2000)
            {
                minim=j;
            }
        }
        m.x=minim;
        m.y=v[minim].first;
        m.c=v[minim].second;
        A.push_back(m);
        cost+=m.c;
        v[minim].second=-2000;
        r=minim;
    }
}

void Graf::citire()
{
    ifstream f ("apm.in");
    f>>N>>M;
    muchie m;
    unsigned long i;
    G=new vector< pair<unsigned long, short> > [N+1];
    for(i=0; i<M; i++)
    {
        f>>m.x>>m.y>>m.c;
        cout<<m.x<<' '<<m.y<<' '<<m.c<<'\n';
        toate.push_back(m);
        G[m.x].push_back(make_pair(m.y, m.c));
        G[m.y].push_back(make_pair(m.x, m.c));
        //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;
}