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

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie{
    int x, y;
    short cost;
}v[400000];

int tata[400000], niv[200000];
vector<muchie> sel;

int fnd(int x)
{
    int y = x, r = x;
    while(tata[r] != 0)
    {
        r = tata[r];
    }
    while(tata[y] != 0)
    {
        int z = tata[y];
        tata[y] = r;
        y = z;
    }
    return r;
}

void uni(int t1, int t2)
{
    if(t1 != t2)
    {
        if(niv[t1] < niv[t2])
        {
            tata[t1] = t2;
        }
        else if(niv[t1] > niv[t2])
        {
            tata[t2] = t1;
        }
        else{
            tata[t2] = t1;
            niv[t1]++;
        }
    }
}

int main()
{
    int n, m;
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> v[i].x >> v[i].y >> v[i].cost;
    }
    sort(v + 1, v + m + 1, [](muchie m1, muchie m2){
        return m1.cost < m2.cost;
    });
    int nr = 0, cost = 0;
    for(int i = 1; i <= m; i++)
    {
        int t1 = fnd(v[i].x);
        int t2 = fnd(v[i].y);
        if(t1 != t2)
        {
            nr++;
            //fout << v[i].x << ' ' << v[i].y << '\n';
            cost += v[i].cost;
            sel.push_back(v[i]);
            uni(t1, t2);
        }
    }
    fout << cost << '\n' << nr << '\n';
    for(int i = 0; i < sel.size(); i++)
    {
        fout << sel[i].x << ' ' << sel[i].y << '\n';
    }


    return 0;
}