#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

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

struct Edge{
    int u, v, w;
    bool operator<(const Edge &m) const{
        return w < m.w;
    }
};

int n, m, cost;
vector<Edge> apcm, edg;

int find(int x, vector<int> &tata){
    if(tata[x]==0){
        return x;
    }
    return find(tata[x], tata);
}

void unire(int x, int y, vector<int> &tata, vector<int> &rang){
    int rx = find(x, tata);
    int ry = find(y, tata);
    if(rx != ry){
        if(rang[rx] < rang[ry]) swap(rx, ry);
        tata[ry] = rx;
        if(rang[rx] == rang[ry]) rang[rx]++;
    }
}

int main(){
    fin>>n>>m;
    while(m--){
        Edge e;
        fin>>e.u>>e.v>>e.w;
        edg.push_back(e);
    }
   ;
    sort(edg.begin(), edg.end());
    vector<int> tata(n+1, 0), rang(n+1, 0);
    for(auto &e : edg){
        if(apcm.size() == n-1)
            break;

        if(find(e.u, tata) != find(e.v, tata)){
            cost += e.w;
            apcm.push_back(e);
            unire(e.u, e.v, tata, rang);
        }
    }
    fout<<cost<<'\n';
    fout<<apcm.size()<<'\n';
    for(auto &e : apcm){
        fout<<e.u<<" "<<e.v<<'\n';
    }
    fout.close();
    return 0;
}