#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <set>


using namespace std;
ifstream f("apm.in" );
ofstream g("apm.out");

int N, M;
vector< pair<int, int> > A[200001], result[200001];

int used[200001], dist[200001], origin[200001];

int main()
{
    f >> N >> M;

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

        A[x].push_back( make_pair(y, c) );
        A[y].push_back( make_pair(x, c) );
    }
    memset(dist, 16, sizeof dist);

    int apm = 0;
    set< pair<int, int> > unseen;
    used[1] = 1;
    for ( vector< pair<int, int> >::iterator it = A[1].begin(); it!=A[1].end(); it++ )
    {
        dist  [(*it).first] = (*it).second;
        origin[(*it).first] = 1;
        unseen.insert( make_pair((*it).second, (*it).first) );
    }
    // Initializare apm


    while ( !unseen.empty() )
    {
        int act = (*unseen.begin()).second;
        int cost = (*unseen.begin()).first;
        unseen.erase(unseen.begin());

        apm+=cost; used[act] = 1;
        int x = origin[act];
        int y = act;

        result[x].push_back( make_pair(y, cost) );

        for ( vector< pair<int, int> >::iterator it = A[act].begin(); it!=A[act].end(); it++ )
            if ( !used[(*it).first] )
            {
                int nod = (*it).first;
                int costnod = (*it).second;

                unseen.erase ( make_pair(dist[nod], nod) );
                if ( costnod < dist[nod] )
                {
                    dist[nod] = costnod;
                    origin[nod] = act;
                }

                unseen.insert( make_pair(dist[nod], nod) );
            }
    }

    g << apm << '\n';
    g << N-1 << '\n';
    for ( int i=1; i<=N; i++ )
        for ( vector< pair<int, int> >::iterator it = result[i].begin(); it!=result[i].end(); it++ )
            g << i << ' ' << (*it).first << '\n';
}