#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

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

#define cin fin
#define cout fout

const int MMax = 400005;

pair <int, int> p[MMax];
int k;

int n, m, total;
int tata[MMax], rg[MMax];

struct Muchie{
    int x, y, cost;
} v[MMax], afisare[MMax];

bool comp(Muchie a, Muchie b) {
    return a.cost < b.cost;
}

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

    sort(v+1, v+m+1, comp);

    for(int i=1; i<=n; i++)
    {
        rg[i] = 1;
        tata[i] = i;
    }
}

int gasire_tata(int nod)
{
    while(tata[nod] != nod)
    {
    nod = tata[nod];
    }
    return nod;
}

void unire(int x, int y)
{
    if(rg[x] < rg[y])
    {
        tata[x] = y;
    }
    if(rg[x] > rg[y])
    {
        tata[y] = x;
    }

    if(rg[x] == rg[y])
    {
        tata[x] = y;
        rg[y]++;
    }
}

int costisitor;

void solve()
{
    for(int i=1; i<=m; i++)
    {
        if(gasire_tata(v[i].x) != gasire_tata(v[i].y))
        {
            unire(gasire_tata(v[i].x), gasire_tata(v[i].y));
            p[++k].first = v[i].x;
            p[k].second = v[i].y;
            costisitor = costisitor + v[i].cost;
        }
    }

    cout << costisitor << endl;
    cout << k << endl;
    for(int i=1; i<=k; i++)
    {
        cout << p[i].first << " " << p[i].second << endl;
    }
}

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