#include <bits/stdc++.h>
#define NMAX 200004

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

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

struct comparare
{
    bool operator() (const Muchie & a, const Muchie & b)
    {
        return a.cost > b.cost;
    }
};

int n, m, cost_total;
int tata[NMAX], h[NMAX];
priority_queue <Muchie, vector <Muchie>, comparare> H;
vector < pair <int, int> > sol;

void citire();
void Kruskal();
int Find(int x);
void Union(int x, int y);
void afisare();

int main()
{
    citire();
    Kruskal();
    afisare();
    return 0;
}

void citire()
{
    Muchie M;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> M.x >> M.y >> M.cost;
        H.push(M);
    }
}

void Kruskal()
{
    Muchie M;
    while (!H.empty())
    {
        M = H.top();
        H.pop();

        int c1 = Find(M.x);
        int c2 = Find(M.y);
        if (c1 != c2)
        {
            Union(c1, c2);
            cost_total += M.cost;
            sol.push_back({M.x, M.y});
        }
    }
}

void afisare()
{
    fout << cost_total << '\n';
    fout << sol.size() << '\n';
    for (int i = 0; i < sol.size(); i++)
        fout << sol[i].first << ' ' << sol[i].second << '\n';
}

int Find(int x)
{
    int root = x, aux;
    while (tata[root])
        root = tata[root];

    while (tata[x])
    {
        aux = tata[x];
        tata[x] = root;
        x = tata[x];
    }

    return root;
}

void Union(int x, int y)
{
    if (h[x] < h[y])
        tata[x] = y;
    else if (h[x] > h[y])
        tata[y] = x;
    else
    {
        tata[x] = y;
        h[y]++;
    }
}