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

using namespace std;

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

struct Edge {
    int v1, v2, cost;
    Edge(int x, int y, int z) {
        v1 = x; v2 = y; cost = z;
    }
};

vector<Edge> EDGES;
vector<int> RANK, LEADER;
vector<pair<int, int> >SOL;
int n, m;
long total;


int Find(int v) {
    if(LEADER[v] == 0) return v;
    else return Find(LEADER[v]);
}

void Union(int r1, int r2) {
    if(RANK[r1]<RANK[r2]) {
        LEADER[r1] = r2;
    } else if(RANK[r2]<RANK[r1]) {
        LEADER[r2] = r1;
    } else {
        LEADER[r2] = r1;
        RANK[r1] ++;
    }
}

bool cmp(Edge a, Edge b) {
    return a.cost < b.cost;
}

int main() {
    fin>>n>>m;
    int a, b, c;
    for(int i=1; i<=m; i++) {
        fin>>a>>b>>c;
        EDGES.push_back(Edge(a, b, c));
    }

    RANK.resize(n+1, 0);
    LEADER.resize(n+1, 0);

    sort(EDGES.begin(), EDGES.end(), cmp);

    int v1, v2, r1, r2;
    for(int i=0; i<m; i++) {
        v1 = EDGES[i].v1;
        v2 = EDGES[i].v2;
        r1 = Find(v1);
        r2 = Find(v2);
        if(r1 != r2) {
            Union(r1, r2);
            SOL.push_back(make_pair(v1, v2));
            total += EDGES[i].cost;
        }
    }

    fout<<total<<'\n'<<n-1<<'\n';
    for(int i=0; i<SOL.size(); i++) {
        fout<<SOL[i].first<<" "<<SOL[i].second<<'\n';
    }
    return 0;
}