#include <fstream>
#include <algorithm>

using namespace std;

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

struct muchie{
    int x, y;
    int cost;
}M[400005];

int n, m;
int p[200005];

void Union(int poz1, int poz2)
{
    p[poz1] = poz2;
}

int rad(int poz)
{
    if(p[poz] != poz)
        return rad(p[poz]);
    else
        return poz;
}
bool functie(muchie a, muchie b)
{
    return a.cost < b.cost;
}
int cnt;
int suma;
int v[400005];
int main()
{
    cin >> n;
    cin >> m;
    for(int i = 1; i <= n; i++)
        p[i]=i;
    for(int i = 1; i <= m; i++)
        cin >> M[i].x >> M[i].y >> M[i].cost;
    sort(M+1, M+m+1, functie);
    int poz = 1;
    while(cnt < n-1)
    {
        if(rad(M[poz].x) != rad(M[poz].y))
        {
            Union(M[poz].x,M[poz].y);
            cnt++;
            suma += M[poz].cost;
            v[cnt] = poz;
        }
        poz++;
    }
    cout << suma<<'\n'<<cnt<<'\n';
    for(int i = 1; i <= cnt; i++)
    {
        int a = v[i];
        cout << M[a].x<<' '<<M[a].y<<'\n';
    }


    return 0;
}