#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

struct muchie{
int m1, m2, cost;
bool operator <(const muchie& m) const
{
    return cost < m.cost;
}
};

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

vector<int> h, t;
vector<muchie> g, arb;
int n, m, cosmin;

int main()
{
    fin >> n >> m;
    h = vector<int> (m + 1);
    t = vector<int> (m + 1);
    g = vector<muchie> (m + 1);
   // arb = vector<muchie>(m + 1);
    for (int i = 1; i <= m; i++)
    {
        int x, y, z;
        fin >> x >> y >> z;
        g.push_back({x, y, z});
    }
    sort (g.begin(), g.end());
    for (int i = 0; i <= m; i++)
        t[i] = i;
    Kruskal();
    fout << cosmin << '\n';
    fout << n - 1 << '\n';
    for ( auto e : arb)
        fout << e.m1 << " " << e.m2 << '\n';
}

void Kruskal()
{
    int k = 0, c1, c2;
    for (const auto& e : g)
    {
        int c1 = Find(e.m1);
        int c2 = Find(e.m2);
        if(c1 != c2)
        {
            cosmin += e.cost;
            Union(c1, c2);
            arb.push_back(e);
            if(k == n - 1)
                break;
        }
    }
}

int Find(int x)
{
    if(t[x] == x)
        return x;
    return t[x] = Find(t[x]);

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