#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fi("apm.in");
ofstream fo("apm.out");
int n, m, i, j, k,cost, vz[200001], rez[200001][2], rz;
vector<pair<int, int>>v[200001];
struct muchie { int x, y, z; } aux, aux2;
struct comp {
    bool operator()(muchie a, muchie b)
    {
        return (a.z > b.z);
    }
};
priority_queue<muchie,vector<muchie>,comp>q;
int main()
{
    int nrm = 0;
    unsigned int a;
    fi >> n >> m;
    while (fi >> i >> j >> k)
    {
        v[i].push_back(make_pair(j, k));
        v[j].push_back(make_pair(i, k));
    }
    vz[1] = 1;
    for (a = 0; a < v[1].size(); a++)
    {
        aux.x = 1;
        aux.y = v[1][a].first;
        aux.z = v[1][a].second;
        q.push(aux);
    }
    while (nrm < n - 1)
    {
        aux = q.top();
        q.pop();
        if (vz[aux.y] == 0)
        {
            nrm++;
            rz++;
            rez[rz][0] = aux.x;
            rez[rz][1] = aux.y;
            cost += aux.z;
            vz[aux.y] = 1;
            for (a = 0; a < v[aux.y].size(); a++)
            {
                 aux2.x = aux.y;
                 aux2.y = v[aux.y][a].first;
                 aux2.z = v[aux.y][a].second;
                 q.push(aux2); 
            }
        }
    }
    fo << cost << '\n' << rz << '\n';
    for (i = 1; i <= rz; i++)
        fo << rez[i][0] << " " << rez[i][1] << '\n';
    return 0;
}