#include <fstream>
#include <algorithm>
#define NMAX 200002
#define MMAX 400002
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct Muchie 
{
    int x, y, c;
};
Muchie v[MMAX], sol[NMAX];
bool cmp(Muchie a, Muchie b) 
{
    return a.c < b.c;
}
int tata[NMAX], h[NMAX];
void Union(int rx,int ry) //regula de ponderare
{
    if(h[rx]>h[ry]) tata[ry]=rx;
    else if(h[rx]<h[ry]) tata[rx]=ry;
        else{
            tata[rx]=ry;
            h[ry]++;
        }
}
int find(int x) //returneaza rad arborelui in care se afla x
{
    int rad=x, y;
    while(tata[rad]) rad=tata[rad];
    while(x!=rad)
    {
        y=tata[x];
        tata[x]=rad;
        x=y;
    }
    return rad;
}

int main() 
{
    int n, m, rx,ry;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
        fin >> v[i].x >> v[i].y >> v[i].c;
    sort(v + 1, v + m + 1, cmp);

    int s = 0, nr = 0;
    for (int i = 1; i <= m; i++) 
    {
        int x = v[i].x;
        int y = v[i].y;
        rx=find(x);
        ry=find(y);
        if (rx!=ry) 
        {
            s += v[i].c;
            nr++; 
            sol[nr] = v[i];
            Union(rx,ry);
            if (nr == n - 1)
                break;
        }
    }
    fout << s << '\n';
    fout << nr << '\n';
    for (int i = 1; i <= nr; i++)
        fout << sol[i].x << ' ' << sol[i].y << '\n';
    return 0;
}