#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

struct edg {
    int x,c,t;
};

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

vector<tuple<int, int, int>> v[200003];
pair<int, int> e[400003];
bool viz[200003];
bool viz2[200003];

int main() {

    int n,m;
    in >> n >> m;
    int x,y,c;
    tuple<int, int, int> a;

    for(int i = 1; i <= m; i++) {
        in >> x >> y >> c;
        get<1>(a) = y;
        get<0>(a) = -c;
        get<2>(a) = i;
        v[x].push_back(a);
        get<1>(a) = x;
        v[y].push_back(a);
        e[i] = {x, y};
    }

    priority_queue<tuple<int, int, int>> Q;
    for(int i = 0; i < v[1].size(); i++)
        Q.push(v[1][i]);

    viz2[1] = 1;
    int ct = 0;
    int am = 0;

    while(!Q.empty()) {

        a = Q.top();
        Q.pop();

        if(viz[get<2>(a)])
            continue;
        if(viz2[get<1>(a)])
            continue;

        viz[get<2>(a)] = true;
        viz2[get<1>(a)] = true;
        ct += -get<0>(a);
        am++;

        for(int i = 0; i < v[get<1>(a)].size(); i++) {
            if(viz[get<2>(v[get<1>(a)][i])])
                continue;
            if(viz2[get<1>(v[get<1>(a)][i])])
                continue;
            Q.push(v[get<1>(a)][i]);
        }

    }

    out << ct << '\n';
    out << am << '\n';

    for(int i = 1; i <= m; i++) {
        if(!viz[i])
            continue;
        out << e[i].first << " " << e[i].second << '\n';
    }

    return 0;
}