#include <fstream>
#include <vector>
#define inf 2000000000

using namespace std;

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

const int Nmax = 4005;

struct punct
{
    int a;
    int b;
}muchie[Nmax];

int n, m, x, y, val, nrv, rez, CostMin, VfMin;
int cmin[Nmax], p[Nmax];
int cost[Nmax][Nmax];
bool OK[Nmax];

vector <int> A[Nmax];

int main()
{
    in >> n >> m;
    nrv = n - 1;

    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            cost[i][j] = inf, cost[j][i] = inf;

    for (int i = 1; i <= m; i++)
    {
        in >> x >> y >> val;

        A[x].push_back(y);
        A[y].push_back(x);
        cost[x][y] = val;
        cost[y][x] = val;
    }

    for (int i = 1; i <= n; i++)
    {
        cmin[i] = cost[1][i];
        p[i] = 1;
    }

    OK[1] = 1;

    while (nrv)
    {
        CostMin = inf;

        for (int i = 1; i <= n; i++)
            if (OK[i] == 0 && CostMin > cmin[i])
            {
                CostMin = cmin[i];
                VfMin = i;
            }

        OK[VfMin] = 1;
        nrv--;

        for (auto i = 0; i < A[VfMin].size(); i++)
        {
            int x = A[VfMin][i];
            if (OK[x] == 0 && cost[x][VfMin] < cmin[x])
            {
                cmin[x] = cost[x][VfMin];
                p[x] = VfMin;
            }
        }
    }

    for (int i = 2; i <= n; i++)
    {
        muchie[i].a = i;
        muchie[i].b = p[i];
        rez = rez + cost[i][p[i]];
    }

    out << rez << '\n';
    out << n - 1 << '\n';

    for (int i = 2; i <= n; i++)
        out << muchie[i].a << ' ' << muchie[i].b << '\n';

    return 0;
}