/*
https://infoarena.ro/problema/apm
*/
#include <fstream>
#include <vector>

using namespace std;

const int INF = 2e8;

struct muchie
{
    int x, y, c;
    int celalalt(int vf)
    {
        return (x + y - vf);
    }
};

vector <int> h, d, poz_in_h;

void schimb(int p1, int p2)
{
    swap(h[p1], h[p2]);
    poz_in_h[h[p1]] = p1;
    poz_in_h[h[p2]] = p2;
}

int tata(int x)
{
    return (x - 1) / 2;
}

int fiu_stang(int x)
{
    return 2 * x + 1;
}

int fiu_drept(int x)
{
    return 2 * x + 2;
}

void adauga(int x)
{
    h.push_back(x);
    poz_in_h[x] = (int)h.size() - 1;
}

void coboara(int p)
{
    int fs = fiu_stang(p), fd = fiu_drept(p), p_min = p;
    if (fs < (int)h.size() && d[h[fs]] < d[h[p_min]])
    {
        p_min = fs;
    }
    if (fd < (int)h.size() && d[h[fd]] < d[h[p_min]])
    {
        p_min = fd;
    }
    if (p_min != p)
    {
        schimb(p, p_min);
        coboara(p_min);
    }
}

void sterge()
{
    schimb(0, (int)h.size() - 1);
    h.pop_back();
    coboara(0);
}

void urca(int p)
{
    while (p > 0 && d[h[p]] < d[h[tata(p)]])
    {
        schimb(p, tata(p));
        p = tata(p);
    }
}

int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");
    int n, m;
    in >> n >> m;
    vector <muchie> e(m);
    vector <vector <int>> lst_a(n + 1);
    for (int i = 0; i < m; i++)
    {
        in >> e[i].x >> e[i].y >> e[i].c;
        lst_a[e[i].x].push_back(i);
        lst_a[e[i].y].push_back(i);
    }
    in.close();
    d.resize(n + 1, INF);
    poz_in_h.resize(n + 1, -1);
    d[1] = 0;
    for (int i = 1; i <= n; i++)
    {
        adauga(i);
    }
    int cost = 0;
    vector <int> vecin_apm(n + 1, 0);
    vector <bool> in_apm(n + 1, false);
    while (!h.empty())
    {
        int x = h[0];
        sterge();
        in_apm[x] = true;
        cost += d[x];
        for (auto i: lst_a[x])
        {
            int y = e[i].celalalt(x);
            if (!in_apm[y] && e[i].c < d[y])
            {
                d[y] = e[i].c;
                urca(poz_in_h[y]);
                vecin_apm[y] = x;
            }
        }
    }
    out << cost << "\n" << n - 1 << "\n";
    for (int i = 2; i <= n; i++)
    {
        out << i << " " << vecin_apm[i] << "\n";
    }
    out.close();
    return 0;
}