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

using namespace std;

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

const int nmax = 200000;
vector<pair<int, int>> graf[nmax + 1];
vector<int> muchiiPrim;

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int d[nmax + 1], t[nmax + 1], viz[nmax + 1];
int n, m, suma;

void citireGraf()
{
    fin >> n >> m;

    for(int i = 0; i < m; i++)
    {
        int x, y, z;

        fin >> x >> y >> z;

        graf[x].push_back(make_pair(y, z));
        graf[y].push_back(make_pair(x, z));
    }
}

void initializareAux()
{
    for(int i = 1; i <= n; i++)
        d[i] = 1e9;
}

void startPrim(int nodStart)
{
    suma = d[nodStart] = 0;

    pq.push(make_pair(d[nodStart], nodStart));

    while(!pq.empty())
    {
        int x  = pq.top().second;

        pq.pop();

        if(viz[x])
            continue;

        viz[x] = 1;
        suma += d[x];

        for(auto nextNode : graf[x])
        {
            if(!viz[nextNode.first] && d[nextNode.first] > nextNode.second)
            {
                d[nextNode.first] = nextNode.second;

                t[nextNode.first] = x;

                pq.push(make_pair(d[nextNode.first], nextNode.first));
            }
        }
    }
}

void afisareRezultat()
{
    fout << suma << endl << n - 1 << endl;

    for(int i = 2; i <= n; i++)
        fout << t[i] << " " << i << endl;
}


int main()
{
    citireGraf();

    initializareAux();

    startPrim(1);

    afisareRezultat();

    fin.close();
    fout.close();

    return 0;
}