#include <fstream>
#include <vector>
#include <algorithm>
#define Nmax 200005
using namespace std;

vector <pair< int, pair<int, int> > > edges;
vector <pair <int, int> > apm;
int parent[Nmax];
int n, m;
int apm_edges = 0, apm_cost = 0;
bool cmp(const pair <int, pair< int, int > > &a, const pair <int, pair <int, int> > &b){
    return a.first < b.first;
}
int findparent(int i){
    int root = i;
    while(parent[root] != root){
        root = parent[root];
    }
    //path compression = facem lantul de la i la radacina sa aiba acelasi tata, in vectorul de tati parent
    while(i != root){
        int next = parent[i];
        parent[i] = root;
        i = next;
    }
    return root;
}
void unify(int x, int y){
    int px = findparent(x);
    int py = findparent(y);
    parent[px] = py;
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");

    f >> n >> m;
    int a, b, c;

    for(int i = 0; i < m; ++i){
        f >> a >> b >> c;
        edges.push_back(make_pair(c, make_pair(a, b)));
    }
    //initializam vectorul de tati
    for(int i = 0; i < n; ++i){
        parent[i] = i;
    }
    //sortam muchiile dupa cost
    sort(edges.begin(), edges.end(), cmp);
    for(int i = 0; i < m; ++i){
        //extragem din edges, nodul sursa, destinatia si costul
        a = edges[i].second.first;
        b = edges[i].second.second;
        c = edges[i].first;
        if(findparent(a) != findparent(b)){
            unify(a, b);
            apm_cost += c;
            apm_edges += 1;
            apm.push_back(make_pair(a, b));
        }
         if(apm_edges == n - 1){
            break;
        }
    }
    g << apm_cost << "\n";
    g << apm_edges << "\n";
    unsigned int sz = apm.size();
    for(unsigned int i = 0; i < sz; ++i){
        g << apm[i].first << " " << apm[i].second << "\n";
    }
    f.close();
    g.close();
    return 0;
}