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

using namespace std;

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

struct edge{
    int a,b,c;
};

const int NMAX = 200005;
vector<int> adj[NMAX];
vector<edge> edges;
bool viz[NMAX];
int n,m;

bool isSameComp(int a, int b) {
    queue<int> q;
    q.push(a);
    for (int i=1;i<=n;i++) {
        viz[i] = false;
    }
    viz[a] = true;
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        if (p == b) {
            return true;
        }
        for (auto v : adj[p]) {
            if (viz[v] == false) {
                viz[v] = true;
                q.push(v);
            }
        }
    }
    return false;
}

bool cmp(edge a, edge b) {
    return a.c < b.c;
}

void kruskal() {
    int ans = 0;
    vector<pair<int,int>> ansE;
    for (auto e : edges) {
        if (!isSameComp(e.a,e.b)) {
            adj[e.a].push_back(e.b);
            adj[e.b].push_back(e.a);
            ans += e.c;
            ansE.push_back({e.a,e.b});
        }
    }
    fout<<ans<<'\n';
    fout<<ansE.size()<<'\n';
    for (auto e : ansE) {
        fout<<e.first<<" "<<e.second<<'\n';
    }
}

int main()
{
    fin>>n>>m;
    int x,y,c;
    for (int i=1;i<=m;i++) {
        fin>>x>>y>>c;
        edges.push_back({x,y,c});
    }
    sort(edges.begin(),edges.end(),cmp);
    kruskal();
    return 0;
}