#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

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

bool rule(muchie A, muchie B)
{
    if (A.cost == B.cost)
    {
        if (A.x == B.x)
            return A.y < B.y;
        return A.x < B.x;
    }
    return A.cost < B.cost;
}

bool Kruskal(muchie A, int &CompNr, vector<int> &Component, vector<int> &comp_size)
{
    if (Component[A.x] == Component[A.y])
    {
        if (Component[A.x] == -1)
        {
            comp_size[CompNr]+= 2;
            Component[A.x] = CompNr;
            Component[A.y] = CompNr;
            CompNr++;
            return true;
        }
        return false;
    }

    if (Component[A.x] == -1 || Component[A.y] == -1)
    {
        if (Component[A.y] == -1)
            swap(A.x, A.y);
        Component[A.x] = Component[A.y];
        comp_size[Component[A.y]]++;
        return true;
    }

    int C = Component[A.y];
    for (int i = 0; i < Component.size() && comp_size[C] != 0; i++)
        if (Component[i] == C)
        {
            Component[i] = Component[A.x];
            comp_size[C]--;
            comp_size[Component[A.x]]++;
        }

    return true;
}
int main()
{
    ios_base::sync_with_stdio(false);

    int n, m, S = 0, CompNr = 0, nr = 0;
    in>> n >> m;

    vector<int> comp_size(n + 1, 0);
    vector<int> Component(n, -1);
    vector<muchie> M(m);
    vector<pair<int, int>> Apm (n - 1);

    for (int i = 0; i < m; i++)
    {
        muchie A;
        in>> A.x >> A.y >> A.cost;
        A.x--; A.y--;
        M[i] = A;
    }

    sort(M.begin(), M.end(), rule);

    for (int i = 0; i < m; i++)
        if (Kruskal(M[i], CompNr, Component, comp_size))
        {
            S+= M[i].cost;
            Apm[nr] = make_pair(M[i].x, M[i].y);
            nr++;
        }

    out<< S << "\n";
    out<< nr << "\n";
    for (int i = 0; i < nr; i++)
        out<< Apm[i].first + 1 << " " << Apm[i].second + 1<< "\n";

    return 0;
}