#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define Nmax 100004

class node
{
    public:

        node(){ };

        int vecin;
        int cost;
};

class edge
{
    public:

        edge(){ };

        int eu;
        int vecin;
        int cost;
};

class compare
{
    public:

        bool operator() ( edge &a, edge &b ) const
        {
            return a.cost > b.cost;
        }
};

priority_queue < edge, vector< edge >, compare > Heap;

vector< node > G[Nmax];
vector< edge > v(Nmax);
vector< bool > used(Nmax);

int N, M, P, SUM;

void read()
{
    ifstream f("apm.in");

    f >> N >> M;

    for ( int i = 1, a, b, c; i <= M; ++i )
    {
        f >> a >> b >> c;

        node x;
        x.cost = c;

        x.vecin = b;
        G[a].push_back( x );

        x.vecin = a;
        G[b].push_back( x );
    }

    f.close();
}

void PrimMST()
{
    int remain = N - 1;
    int nod = 1;
    vector< node >::iterator it;
    used[nod] = 1;

    while( remain )
    {
        for ( it = G[nod].begin(); it != G[nod].end(); ++ it )
                if ( !used[ it->vecin ] )
                {
                    edge x;

                    x.eu = nod;
                    x.vecin = it->vecin;
                    x.cost = it->cost;

                    Heap.push( x );
                }

        edge old = Heap.top();
        Heap.pop();

        while( used[ old.vecin ] )
                old = Heap.top(),
                Heap.pop();

        SUM += old.cost;
        v[ ++P ] = old;

        nod = old.vecin;
        used[nod] = 1;
        remain--;
    }
}

void print()
{
    ofstream g("apm.out");

    g << SUM << "\n" << N - 1 << "\n";

    for ( int i = 1; i < N; ++i )
            g << v[i].eu << " " << v[i].vecin << "\n";

    g.close();
}

int main()
{
    read();
    PrimMST();
    print();

    return 0;
}