//
//  main.cpp
//  kruskal aparent
//
//  Created by Radu Costache on 02/01/2021.
//  Copyright © 2021 Radu Costache. All rights reserved.
//

#include <fstream>
#include <algorithm>

#define MMAX 400005
#define NMAX 200005

using namespace std;

class muc {
public:
    int x, y, c;
    bool taken;
    friend istream & operator>>(istream &in, muc &tmp) {
        in >> tmp.x >> tmp.y >> tmp.c;
        return in;
    }
};

int n, m;
int cmin, nedges;
int Parent[NMAX], rang[NMAX];
muc edge[MMAX];


inline void read();
inline void print();
inline void solve();

inline void init();
inline void Kruskal();

inline int Find(int);
inline void Union(int, int);

bool cmp(muc &, muc &);

int main(int argc, const char * argv[]) {
    // insert code here...
    read();
    solve();
    print();
    return 0;
}

inline void read() {
    ifstream f("kruskal.in");
    f >> n >> m;
    for (int i = 1; i <= m; ++i)
        f >> edge[i];
    f.close();
}

inline void solve() {
    init();
    Kruskal();
}

inline void print() {
    ofstream g("kruskal.out");
    g << cmin << '\n' << nedges << '\n';
    for (int i = 1; i <= m; ++i) {
        if (edge[i].taken == 1)
            g << edge[i].x << ' ' << edge[i].y << '\n';
    }
    g.close();
}

inline void init() {
    for (int i = 1; i <= n; ++i)
        Parent[i] = i;
    sort(edge + 1, edge + m + 1, cmp);
}

inline void Kruskal() {
    for (int i = 1; i <= m; ++i)
        if (Find(edge[i].x) != Find(edge[i].y)) {
            Union(edge[i].x, edge[i].y);
            cmin += edge[i].c;
            edge[i].taken = 1;
            ++nedges;
        }
}

inline int Find(int node) {
    if (Parent[node] != node)
        Parent[node] = Find(Parent[node]);
    return Parent[node];
}
 
inline void Union(int x, int y) {
    int px = Find(x);
    int py = Find(y);
    
    if (px == py)
        return;
    if (rang[px] < rang[py])
        Parent[px] = py;
    else if (rang[px] > rang[py])
        Parent[py] = px;
    else {
        Parent[px] = py;
        ++rang[py];
    }
    
}

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