#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
#define N_MAX 200005
int n, m, viz[N_MAX], rez, tata[N_MAX];
vector<pair<int, int> > G[N_MAX];
///         dist       nod  tata
priority_queue<pair <int, pair <int, int> > > pq;

void apm()
{
    pq.push(make_pair(0, make_pair(1, 1)));
    while(!pq.empty())
    {
        pair<int, pair<int, int> > _top = pq.top();
        pq.pop();
        int nod = _top.second.first;
        if(viz[nod])
           continue;
        viz[nod] = 1;
        rez += -_top.first;
        tata[nod] = _top.second.second;
        for(auto it: G[nod])
            pq.push(make_pair(-it.second, make_pair(it.first, nod)));
    }
}

int main()
{
    f >> n >> m;
    int x, y, z;
    for(int i = 1; i <= m; i++)
    {
        f >> x >> y >> z;
        G[x].push_back(make_pair(y,z));
        G[y].push_back(make_pair(x,z));
    }
    apm();
    g << rez << '\n' << n - 1 <<"\n";
    for(int i = 2; i <= n; i++)
        g << i << " " << tata[i] << "\n";
    return 0;
}