#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define f first
#define s second
#define sf second.first
#define ss second.second

using namespace std;

bool b[200005];
vector <pair <int, int> > mat[200005];
vector <pair <int, int> > :: iterator it, itf;
pair <int, int> v[200005];
priority_queue <pair <int, pair <int, int> > > q;
pair <int, pair <int, int> > p;

int main()
{
    //ifstream in ("date.in");/*
    ifstream in ("apm.in");
    ofstream out ("apm.out");//*/

    int n, m, x, y, c, i, nrt = 0, nrv = 0;
    in >> n >> m;
    for (i = 0; i < m; ++i){
        in >> x >> y >> c;
        mat[x].push_back ({y, c});
        mat[y].push_back ({x, c});
    }
    b[1] = 1;
    itf = mat[1].end();
    for (it = mat[1].begin(); it != itf; ++it) {
        q.push ({-it->s, {1, it->f}});
    }

    m = n - 1;
    while (m) {
        p = q.top();
        q.pop();
        if (b[p.sf] == 0) {x = p.sf;}
        else {
            if (b[p.ss] == 0) {x = p.ss;}
            else {continue;}
        }
        nrt -= p.f;
        --m;
        v[++nrv] = p.s;
        b[x] = 1;
        itf = mat[x].end();
        for (it = mat[x].begin(); it != itf; ++it) {
            if(b[it->f] == 0) {
                q.push ({-it->s, {x, it->f}});
            }
        }
    }

    out << nrt << "\n" << n-1 << "\n";
    for (i = 1; i <= nrv; ++i){
        out << v[i].f << " " << v[i].s << "\n";
    }

    return 0;
}