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

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

const int N=2e5;
const int M=4e5;

struct muchie
{
    int x, y, c;
};

muchie e[M+1];
bool sel[M];
int t[N+1], nr[N+1], n, total;

bool cmp(muchie e1, muchie e2)
{
    return (e1.c < e2.c);
}

/// returneaza radacina arborelui din care face parte x
int radacina(int x)
{
    if (t[x] == x)
        return x;
    return t[x] = radacina(t[x]);
}

/// returneaza daca x si y se afla in aceeasi multime
bool query(int x, int y)
{
    return radacina(x)==radacina(y);
}


/// uneste pe x si y
void unite(int x, int y)
{
    int rx = radacina(x);
    int ry = radacina(y);

    /// Uniune dupa rang
    if (nr[rx] > nr[ry])
    {
        t[ry] = rx;
        nr[rx] += nr[ry];
        nr[ry] = nr[rx];
    }
    else
    {
        t[rx] = ry;
        nr[ry] += nr[rx];
        nr[rx] = nr[ry];
    }
}

int main()
{
    int m;
    cin >> n >> m;
    for(int i=0; i<m; i++)
    {
        cin >> e[i].x >> e[i].y >> e[i].c;
        t[i] = i;
        nr[i] = 1;
    }
    sort(e, e+m, cmp);
    int n_e = 0, i=0;
    while(n_e < n-1)
    {
        if(!query(e[i].x, e[i].y))
        {
            unite(e[i].x, e[i].y);
            total+=e[i].c;
            sel[i] = true;
            n_e++;
        }
        i++;
    }
    cout << total << '\n';
    cout << n-1 << '\n';
    for(int i=0; i<m; i++)
    {
        if(sel[i] == true)
        {
            cout << e[i].x << " " << e[i].y << '\n';
        }
    }
    return 0;
}