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

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;

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

int main()
{
    int x, y, z;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;
        H.push({x, y, z});
    }
    Kruskal();
    afisare();
    return 0;
}

void Kruskal()
{
    Muchie M;
    while (sol.size() < n-1)
    {
        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});
        }
    }
}

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

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

void afisare()
{
    fout << cost_total << '\n';
    fout << n-1 << '\n';
    for (auto el : sol)
        fout << el.first << ' ' << el.second << '\n';
}