#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

const int NMAX = 200000;
const int MMAX = 400000;

struct Muchie
{
    int u, v, cost, sel = 0;
};

Muchie vv[MMAX + 5];
int t[NMAX + 5], h[NMAX + 5];

bool cmp(Muchie a, Muchie b)
{
    return a.cost < b.cost;
}

int FindSet(int x)
{
    while(x != t[x])
        x = t[x];
    return x;
}

void UnionSet(int x, int y)
{
    if(h[x] == h[y])
    {
        h[x]++;
        t[y] = x;
    }
    else
    {
        if(h[x] < h[y])
        {
            t[x] = y;
        }
        else
            t[y] = x;
    }
}

int main()
{
    int n, m, x, y, c, i, tu, tv, ma, totalc;
    cin >> n >> m;
    
    for(i = 0; i < m; i++)
        cin >> vv[i].u >> vv[i].v >> vv[i].cost;
    
    for(i = 0; i < n; i++)
    {
        t[i] = i;
        h[i] = 1;
    }
    
    sort(vv, vv + m, cmp);
    
    ma = 0; totalc = 0;
    for(i = 0; i < m && ma < n; i++)
    {
        tu = FindSet(vv[i].u);
        tv = FindSet(vv[i].v);
        if(tu != tv)
        {
            ma++;
            vv[i].sel = 1;
            totalc += vv[i].cost;
            UnionSet(tu, tv);
        }
    }
    
    cout << totalc << "\n" << ma << "\n";
    for(i = 0; i < m; i++)
        if(vv[i].sel)
            cout << vv[i].v << " " << vv[i].u << "\n";

    return 0;
}