#include <fstream>

#include <vector>
#include <queue>

#define N 200000
#define M 400000
#define INF 2000

using namespace std;

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

int CT;
int n, m;
bool viz[N + 1];
vector < pair < int, int > > v[N + 1], rasp;

void prim(){
    priority_queue < pair <int, pair <int, int> > > pq;

    pq.push({0, {1, 0}});
    while(!pq.empty()){
        int nc = pq.top().second.first;
        int nod = pq.top().second.second;
        int c = pq.top().first;
        pq.pop();
        if(viz[nc])
            continue;
        CT -= c;
        if(nod)
            rasp.push_back({nod, nc});
        if(!viz[nc]){
            for(int i = 0; i < v[nc].size(); i++){
                int nv = v[nc][i].first;
                int cst = v[nc][i].second;
                if(!viz[nv]){
                    pq.push({-cst, {nv, nc}});
                }
            }
            viz[nc] = true;
        }
    }
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y, c;
        fin >> x >> y >> c;
        v[x].push_back({y, c});
        v[y].push_back({x, c});
    }
    prim();

    fout << CT << '\n';
    fout << n - 1 << '\n';
    for(int i = 0; i < n - 1; i++)
        fout << rasp[i].first << ' ' << rasp[i].second << '\n';

    return 0;
}