#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct MUCHIE
{
    int x,y,c;
    bool sel;
};
vector<MUCHIE>v;
vector<int>t,h;

bool cmp(const MUCHIE &a,const MUCHIE &b)
{
    return a.c < b.c;

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

}

void unifica(int x,int y)
{
    //x si y sunt radacinile arborilor care se unifica
    if(h[x] > h[y])
        t[y] = x;
    else if(h[y]>h[x])
        t[x] = y;
    else
    {
        ++h[x];
        t[y] = x;
    }
}


int main()
{
    int n,m,c,x,y,i,rx,ry,cnt,COST=0;
    MUCHIE temp;
    fin >> n >> m;
    temp = {0,0,0,0};
    v.push_back(temp);
    t.assign(n+1,0);
    h.assign(n+1,1);
    for(i=1; i<=n; ++i)
        t[i] = i;
    for(i=1; i<=m; ++i)
    {
        fin >> temp.x >> temp.y >> temp.c;
        temp.sel = 0;
        v.push_back(temp);

    }
    sort(v.begin()+1,v.end(),cmp);
    cnt = 0;
    for(i=1; i<=m && cnt < n-1; ++i)
    {
        rx =radacina(v[i].x);
        ry = radacina(v[i].y);
        if(rx != ry)
        {
            unifica(rx,ry);
            v[i].sel = 1;
            COST+=v[i].c;
            cnt++;
        }
    }
    fout << COST << "\n" << cnt << "\n";
    for(i=1; i<=m; ++i)
        if(v[i].sel)
            fout << v[i].x <<" " <<v[i].y << "\n";
    fin.close();
    fout.close();
    return 0;

}