#include <bits/stdc++.h>
using namespace std;

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

#define cin fin
#define cout fout

struct tot
{
    int x, y, cost;
} v[400001];

struct afisare
{
    int a, b;
}f[400001];

int frecventa[200001];

int n, m, a, b, c, ez;
int costisitor = 0;

void read()
{
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        cin >> v[i].x >> v[i].y >> v[i].cost;
    }
}

bool comp(tot x, tot y)
{
    return x.cost < y.cost;
}

void atribuire()
{
    for(int i=1; i<=n; i++)
    {
        frecventa[i] = i;
    }
}

void modificare(int a, int b)
{
    for(int i=1; i<=n; i++)
    {
        if(frecventa[i] == b)
        {
            frecventa[i] = a;
        }
    }
}

void solve()
{
    sort(v+1, v+m+1, comp);

    atribuire();

    for(int i=1; i <=m; i++)
    {
        if(frecventa[v[i].x] != frecventa[v[i].y])
        {
            modificare(frecventa[v[i].x], frecventa[v[i].y]);
            costisitor = costisitor + v[i].cost;
            f[++ez].a = v[i].x;
            f[ez].b = v[i].y;
        }
    }

    cout << costisitor << endl;
    cout << ez << endl;

    for(int i=1; i<=ez; i++)
    {
        cout << f[i].a << " " << f[i].b << endl;
    }
}

int main()
{
    read();
    solve();
}