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

using namespace std;

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

struct Edge {
    int vertex1;
    int vertex2;
    int cost;
    Edge(int v1, int v2,int w):vertex1(v1),vertex2(v2),cost(w) {}

};
vector<Edge> v;
vector<Edge> A;
stack<int> q;
int n,m,x,y,z,nr;
int pad[200010];

void uneste(int a, int b) {


    while(pad[a]!=0) {
        q.push(a);
        a=pad[a];
    }
    while(!q.empty()) {
        pad[q.top()]=a;
        q.pop();
    }

    while(pad[b]!=0) {
        q.push(b);
        b=pad[b];
    }
    while(!q.empty()) {
        pad[q.top()]=b;
        q.pop();
    }
    pad[a]=b;
}

bool verifica(int a, int b) {
    while(pad[a]!=0){
        q.push(a);
        a=pad[a];
    }
    while(!q.empty())
    {
        pad[q.top()]=a;
        q.pop();
    }
    while(pad[b]!=0){
        q.push(b);
        b=pad[b];
    }
    while(!q.empty())
    {
        pad[q.top()]=b;
        q.pop();
    }
    if(a==b)
        return 1;
    return 0;

}


void solve() {
    for(auto it:v) {
        if(!verifica(it.vertex1,it.vertex2)) {
            A.push_back(Edge(it.vertex1,it.vertex2,it.cost));
            nr+=it.cost;
            uneste(it.vertex1,it.vertex2);
        }
    }
}

int main() {
    fin>>n>>m;
    while(m--) {
        fin>>x>>y>>z;
        v.push_back(Edge(x,y,z));
    }
    sort(v.begin(),v.end(), [](Edge x, Edge y) {
        return x.cost<y.cost;
    });
    solve();
    fout<<nr<<'\n'<<A.size()<<'\n';
    for(auto it:A)
        fout<<it.vertex1<<' '<<it.vertex2<<'\n';
    return 0;
}