#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

const int NMax = 400005;

int rang[NMax / 2], gr[NMax / 2], n, m, nr;
int x[NMax], y[NMax], c[NMax], indx[NMax];
vector < pair < int, int > > apm;

bool cmp(const int &a, const int &b)
{
    return c[a] < c[b];
}

inline int Find(int x)
{
    int y = x, gr2;
    for(x; gr[x] != x; x = gr[x]);
    gr2 = gr[x];
    x = y;
    while(x != gr2)
    {
        y = gr[x];
        gr[x] = gr2;
        x = y;
    }
    return gr2;
}

inline void Union(int x, int y)
{
    if(rang[x] > rang[y]) gr[y] = x;
    else gr[x] = y;

    if(rang[x] == rang[y]) rang[y]++;
}

int main()
{
    long long cost = 0;
    f >> n >> m;
    for(int i = 1; i <= m ;++i)
    {
        f >> x[i] >> y[i] >> c[i];
        indx[i] = i;
    }
    sort(indx + 1, indx + m + 1, cmp);

    for(int i = 1; i <= n; ++i)
    {
        gr[i] = i;
        rang[i] = 1;
    }

    for(int i = 1; i <= m && nr < n - 1; ++i)
    {
        if(Find( x[ indx[ i ] ] ) != Find( y[ indx[ i ] ] ))
        {
            Union( Find( x[ indx[ i ] ] ), Find( y[ indx[ i ] ]) );
            apm.push_back({x[ indx[ i ] ], y[ indx[ i ] ]});
            cost += c[ indx[ i ] ];
            nr++;
        }
    }
    g << cost << '\n' << n - 1 << '\n';
    for(auto it : apm)
        g << it.first << ' ' << it.second << '\n';
}