#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int start, dest, cost;
}aux, aux1;
struct cmp
{
    bool operator () (edge i, edge j)
    {
        return i.cost > j.cost;
    }
};
priority_queue<edge, vector<edge>, cmp> Heap;
vector <edge> v[200005];
vector <edge> apcm;
bool viz[200005];
int i, n, m, x, y, c, cost_total;
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    f >> n >> m;
    for(i = 1; i <= m; i ++)
    {
        f >> x >> y >> c;
        aux.start = x;
        aux.dest = y;
        aux.cost = c;
        v[x].push_back(aux);
        aux.start = y;
        aux.dest = x;
        v[y].push_back(aux);
    }
    aux.start = 0;
    aux.dest = 1;
    aux.cost = 0;
    Heap.push(aux);
    while(true)
    {
        while(!Heap.empty())
        {
            aux = Heap.top();
            if(viz[aux.dest] == false)break;
            Heap.pop();
        }
        if(Heap.empty())break;
        if(aux.start != 0) //nu este muchia [0, 1] (artificiala)
        {
            apcm.push_back(aux);
            cost_total = cost_total + aux.cost;
        }
        viz[aux.dest] = true;
        for(i = 0; i < v[aux.dest].size(); i ++)
        {
            aux1 = v[aux.dest][i];
            if(viz[aux1.dest] == false)
            {
                Heap.push(aux1);
            }
        }
    }
    g << cost_total << "\n";
    g << apcm.size() << "\n";
    for(i = 0; i < apcm.size(); i ++)
        g << apcm[i].start << " " << apcm[i].dest << "\n";
    return 0;
}