#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>

using namespace std;

const int NMAX = 2 * 1e5 + 1;
const int INF = INT_MAX;

vector <pair<int, int> > a[NMAX];
int d[NMAX], pred[NMAX];
int cost_t;

int prim()
{
    priority_queue <pair<int, int>, vector <pair <int, int> >, greater<pair <int, int> > > h;
    bitset <NMAX> viz;

    d[1] = 0;
    h.push(make_pair(0, 1));

    while(!h.empty())
    {
        int nod = h.top().second;
        h.pop();

        if(!viz[nod])
        {
            cost_t += d[nod];
            viz[nod] = true;
            for(auto y: a[nod])
            {
                if(!viz[y.second] && y.first < d[y.second])
                {
                    d[y.second] = y.first;
                    pred[y.second] = nod;
                    h.push(make_pair(y.first, y.second));
                }
            }
        }
    }

    return cost_t;
}

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

    int n, m;
    fin >> n >> m;

    for(int i = 0; i < m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        a[x].push_back(make_pair(c, y));
        a[y].push_back(make_pair(c, x));
    }

    for(int i = 2; i <= n; i++)
        d[i] = INF;

    fout << prim() << "\n" << n - 1 << "\n";

    for(int i = 2; i <= n; i++)
        fout << pred[i] << " " << i << "\n";


    return 0;
}