//Cu dedicatie
#include <fstream>
#include <vector>
#include <bitset>
#include <algorithm>

using namespace std;

const int   N = 200005,
            M = 2*N;

int n, m;
int x[M] , y[M] , c[M], gr[N], indice[M], rez;
vector<int> apm;

struct cmp{
    bool operator() (const int i, const int j)
    {
        return c[i] < c[j];
    }
};

int padure(int i)
{
    if(gr[i] == i)
        return i;
    gr[i] = padure(gr[i]);
    return gr[i];
}

void reuneste(int i, int j)
{
    gr[padure(i)] = padure(j);
}

int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    cin >> n >> m;
    for(int i = 1 ; i <= m ; ++ i)
    {
        cin >> x[i] >> y[i] >> c[i];
        indice[i] = i;
    }
    sort(indice + 1, indice + m + 1 , cmp());
    for(int i = 1 ; i <= n ; ++ i)
        gr[i] = i;           ///initial fiecare componenta face parte din padurea sa
    for(int i = 1 ; i <= m ; ++ i)
        if( padure(x[indice[i]]) != padure(y[indice[i]]) )
        {
            rez += c[indice[i]];
            reuneste (x[indice[i]], y[indice[i]]);
            apm.push_back(indice[i]);
        }
    cout << rez << "\n" << n-1 << "\n";
    for(vector<int> :: iterator it = apm.begin(), fin = apm.end() ; it != fin ; ++ it)
        cout << x[*it] << " " << y[*it] << "\n";
}