#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<pair<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;
    pair<int, int> a;

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

    priority_queue<pair<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[a.second])
            continue;
        int nx = e[a.second].first;
        if(viz2[nx])
            nx = e[a.second].second;
        if(viz2[nx])
            continue;

        viz[a.second] = true;
        viz2[nx] = true;
        ct += -a.first;
        am++;

        for(int i = 0; i < v[nx].size(); i++) {
            if(viz[v[nx][i].second])
                continue;
            Q.push(v[nx][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;
}