#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
struct apm{
    int a ,b ,cost;
}v[400001];
int n ,m ;
int contor, cost;
int conx[200001];
vector <pair <int,int>> sol;
ifstream cin("apm.in");
ofstream cout("apm.out");
bool cond(apm x, apm y)
{
    return x.cost <y.cost;
}
int main() {
    cin >> n >> m;
    for( int i =1 ;i <=m;i ++)
    {
        cin >> v[i].a >> v[i].b >>v[i].cost;
        conx[i] = i;
    }
    sort(v + 1, v + m + 1, cond);
    for(int i =1 ;i <=m ; i ++)
    {
        if(conx[v[i].a] !=conx[v[i].b])
        {
            sol.push_back({v[i].a, v[i].b});
            int   minim = min(conx[v[i].a],conx[v[i].b]);
           int  maxim = max(conx[v[i].a],conx[v[i].b]);
            cost += v[i].cost;
            contor++;
            if(contor == n - 1)
                break;
            for(int j = 1 ;j <=n; j ++)
                if(conx[j] == maxim)
                    conx[j] = minim;
        }
    }
    cout << cost<<'\n';
    cout << sol.size()<<'\n';
    for(pair<int,int> i: sol)
        cout << i.first << " "<<i.second<<'\n';
    return 0;
}