#include <bits/stdc++.h>

using namespace std;

const int nmax = 400005;

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

int n, m, cost_final, nrel;
int par[nmax], dim[nmax];

struct muchie
{
    int x, y, cost;
    bool operator < (const muchie &A) const{
        return cost < A.cost; ///SORTAM FKIN DESCRESATOR AJKFGJA
    }
}M[2 * nmax], arbore[nmax]; ///2 * nmax are leg cu nr max de muchii in arbore *cred*

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

    sort(M + 1, M + m + 1);
}

int rad(int x)
{
    int aux, sef = x;
    while(par[sef] > 0)
        sef = par[sef];
    while(par[x] > 0) //merg pe toate nodurile de deasupra lui
    {
        aux = par[x];
        par[x] = sef;
        x = aux;
    }
    return sef;
}

int main()
{
    read();

    for(int i = 1; i <= n; i ++)
    {
        par[i] = -1; ///leg fiecare nod de unul imaginar, care sa fie parintele la inceput
        dim[i] = i; ///inca nu inteleg asta smh
    }

    for(int i = 1; i <= m; i ++)
    {
        if(rad(M[i].x) != rad(M[i].y))
        {
            par[rad(M[i].x)] = rad(M[i].y); ///am scris direct, in loc sa pun x (respectiv y) devine rad(x) (sau rad(y))
            dim[rad(M[i].y)] += dim[rad(M[i].x)];
            cost_final += M[i].cost;
            arbore[++nrel] = M[i];
        }
    }

    fout << cost_final << '\n' << nrel << "\n";

    for(int i = 1; i <= nrel; i ++)
        fout << arbore[i].y << " " << arbore[i].x << '\n';
    return 0;
}