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

using namespace std;

int parinte[2019];
ifstream f("apm.in");
ofstream g("apm.out");
vector < pair < int , pair < int , int > > > Edges;
vector < int > k;
vector < int > l;
int Find(int x)
{
    if (parinte[x] == x)
        return x;
    return Find(parinte[x]);
}

void Unite(int x, int y)
{
    int fx = Find(x);
    int fy = Find(y);
    parinte[fx] = fy;
}

int main()
{
    int N, M , x, y, w;

    f >> N >> M;
    for ( int i = 1 ; i <= N ; ++i)
        parinte[i] = i;

    for ( int i = 1 ; i <= M ; ++i)
    {
        f >> x >> y >> w;
        w += 1001;
        Edges.push_back( make_pair( w, make_pair(x,y)) );
    }
    sort ( Edges.begin(),Edges.end() );
    int weight = 0 , edges = 0, nr = 0;
    int i = 0;
    while (weight < N-1 || nr < M)
    {
        int a = Edges[nr].second.first;
        int b = Edges[nr].second.second;
        int w = Edges[nr].first;

       // cout << nr << " " << weight;
        //cin.get();

        if ( Find(a) != Find(b) )
        {
            Unite(a,b);
            weight += w;
            edges ++;

            //cout << b << " " << a << " " << w << endl;
            k.push_back(a);
            l.push_back(b);
        }

        nr++;
    }
    g << weight - (edges*1001) << endl << edges << endl;
    for ( unsigned int i = 0 ; i < k.size() ; ++i)
        g << k[i] << " " << l[i] << endl;

    return 0;
}