#include <bits/stdc++.h>

#if 1
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
#define pb push_back
const int NMax = 2e5 + 5;
const int inf = 1e9 + 5;
const int mod = 9973;
using zint = int;

int N,M;
int dad[NMax],nrArb[NMax];
pair< int, pair<int,int> > edges[NMax];
vector< pair<int,int> > sol;

int findRoot(int);
void unite(int,int);

int main() {
    in>>N>>M;
    for (int i = 1;i <= M;++i) {
        int x,y,c;
        in>>x>>y>>c;

        edges[i] = {c, {x,y}};
    }

    for (int i = 1;i <= N;++i) {
        nrArb[i] = 1;
        dad[i] = i;
    }

    sort(edges + 1, edges + M + 1);

    int costApm = 0;
    for (int i = 1;i <= M;++i) {
        int cost = edges[i].first;
        int x = edges[i].second.first,
            y = edges[i].second.second;

        int rootX = findRoot(x), rootY = findRoot(y);
        if (rootX == rootY) {
            continue;
        }

        unite(rootX,rootY);
        costApm += cost;
        sol.pb( {x,y} );
    }

    out<<costApm<<'\n'<<N-1<<'\n';
    for (auto p : sol) {
        out<<p.first<<' '<<p.second<<'\n';
    }

    in.close();out.close();
    return 0;
}

int findRoot(int node) {
    if (dad[node] == node) {
        return node;
    }

    dad[node] = findRoot(dad[node]);
    return dad[node];
}

void unite(int root1,int root2) {
    if (nrArb[root1] > nrArb[root2]) {
        dad[root2] = root1;
        nrArb[root1] += nrArb[root2];
    }
    else {
        dad[root1] = root2;
        nrArb[root2] += nrArb[root1];
    }
}