#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

struct Node { 
    Node* parent=nullptr;
    int sz=1;
};

Node nodes[200001];

void join(Node *a, Node *b) {
    Node* a_parent;
    Node* b_parent;
    while(a!=nullptr) {
        a_parent=a;
        a=a->parent;
    }
    while(b!=nullptr) {
        b_parent=b;
        b=b->parent;
    }
    b->parent=b_parent;
    a->parent=a_parent;
    if(a_parent->sz<b_parent->sz) {
        a_parent->parent=b_parent;
    } else {
        b_parent->parent=a_parent;
    }
}

bool query(Node* a, Node* b) {
    Node* a_parent;
    Node* b_parent;
    while(b!=nullptr) {
        b_parent=b;
        b=b->parent;
    }
    while(a!=nullptr) {
        a_parent=a;
        a=a->parent;
    }
    return a_parent==b_parent;
}

struct Edge {
    int a, b, cost;
};

int total_cost;
vector<Edge> edges;
vector<Edge> used;
bool cmp(const Edge &e1, const Edge &e2) {
    return e1.cost<e2.cost;
}

int n, m;
int a, b, c;

int main() {
    cin>>n>>m;
    for(int i=0;i<m;i++) {
        cin>>a>>b>>c;
        edges.push_back({a, b, c});
    }
    sort(edges.begin(), edges.end(), cmp);
    for(auto e:edges) {
        Node* a=&nodes[e.a];
        Node* b=&nodes[e.b];
        if(!query(a, b)) {
            join(a, b);
            used.push_back(e);
            total_cost+=e.cost;
        }
    }
    cout<<total_cost<<'\n';
    cout<<used.size()<<'\n';
    for(auto e:used) {
        cout<<e.a<<' '<<e.b<<'\n';
    }
    return 0;
}