#include <fstream>
#include <vector>
#include <utility>

using namespace std;

const int maxn = 200001;
const int inf = 1 << 30;

typedef pair<int, int> PER;

void citire(vector<PER> G[], int &N, int &M)
{
    ifstream in("apm.in");
    in >> N >> M;

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

        G[x].push_back( make_pair(y, c) );
        G[y].push_back( make_pair(x, c) );
    }

    in.close();
}

int prim(vector<PER> G[], int N, PER APM[])
{
    int D[maxn], vec[maxn], k = 0;
    for ( int i = 1; i <= N; ++i )
        D[i] = inf, vec[i] = 1;
    vec[1] = 0;

    vector<PER>::iterator j;
    for ( j = G[1].begin(); j != G[1].end(); ++j )
        D[ j->first ] = j->second;

    int cost = 0;
    for ( int i = 1; i < N; ++i )
    {
        int min = 1;

        for ( int j = 2; j <= N; ++j )
            if ( vec[j] && D[j] < D[min] )
                min = j;

        cost += D[min];
        APM[++k] = make_pair(min, vec[min]);
        vec[min] = 0;

        for ( j = G[min].begin(); j != G[min].end(); ++j )
            if ( vec[ j->first ] && D[ j->first ] > j->second )
            {
                D[ j->first ] = j->second;
                vec[ j->first ] = min;
            }
    }

    return cost;
}

int main()
{
    int N, M;
    vector<PER> G[maxn];

    citire(G, N, M);

    PER APM[maxn - 1];



    ofstream out("apm.out");
    out << prim(G, N, APM) << '\n' << N - 1;
    for ( int i = 1; i < N ; ++i )
        out << APM[i].first << ' ' << APM[i].second << '\n';
    out.close();

    return 0;
}