#include <fstream>
#include <vector>
#define mp make_pair
#define inf 1005

using namespace std;

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

const int Nmax = 200005;

vector <pair <int, int>> A[Nmax];

int main()
{
    int n, m, nrv, rez = 0;
    vector <int> cmin(Nmax), p(Nmax), OK(Nmax);

    in >> n >> m;
    nrv = n - 1;

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

        A[x].push_back(mp (y, val));
        A[y].push_back(mp (x, val));
    }

    for (auto i = 0; i < A[1].size(); i++)
    {
        int x = A[1][i].first;
        int y = A[1][i].second;

        cmin[x] = y;
        p[x] = 1;
    }

    for (int i = 2; i <= n; i++)
        if (!cmin[i])
            cmin[i] = inf;

    OK[1] = 1;

    while (nrv)
    {
        int CostMin = inf;
        int VfMin;

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

        rez = rez + CostMin;

        OK[VfMin] = 1;
        nrv--;

        for (auto i = 0; i < A[VfMin].size(); i++)
        {
            int x = A[VfMin][i].first;
            int w = A[VfMin][i].second;

            if (OK[x] == 0 && w < cmin[x])
            {
                cmin[x] = w;
                p[x] = VfMin;
            }
        }
    }

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

    for (int i = 2; i <= n; i++)
        out << i << ' ' << p[i] << '\n';

    return 0;
}