#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXN 200005
#define ii pair <int, int>
#define pb push_back
#define mp make_pair
#define x first
#define y second

int N, M;
vector < pair <int, ii> > edge;
vector < pair <int, int> > apm;
int p[MAXN], h[MAXN];
int sol;

int cmp (const pair <int, ii> a, const pair <int, ii> b) {
    return a.x < b.x;
}

void read () {
    int a, b, c;
    
    scanf ("%d %d", &N, &M);    
    for (int i = 1; i <= M; ++ i) {
        scanf (" %d %d %d", &a, &b, &c);
        edge.pb(mp (c, mp (a, b)));
    }
}

int root (int n) {
    if (p[n] == n)
        return n;
    return p[n] = root (p[n]);
}

void unite (int n1, int n2) {
    if (h[n1] > h[n2])
        p[n2] = n1;
    else {
        p[n1] = n2;
        if (h[n1] == h[n2])
            ++ h[n2];
    }
}

void Kruskal () {
    int i, cnt = 0;
    
    for (i = 1; i <= N; ++ i) p[i] = i;
    
    for (i = 0; cnt < N - 1; ++ i) {
        int r1 = root (edge[i].y.x), r2 = root (edge[i].y.y);
        if (r1 != r2) {
            unite (r1, r2);
            apm.pb (mp (edge[i].y.x, edge[i].y.y));
            sol += edge[i].x;
            
            ++ cnt;
        }
    }
}

void solve () {
    sort (edge.begin(), edge.end(), cmp);
    
    Kruskal ();
    printf ("%d\n%d\n", sol, apm.size());
    
    for (vector < pair <int, int> > :: iterator it = apm.begin(); it != apm.end(); ++ it) 
        printf ("%d %d\n", it->x, it->y);  
}

int main () {
    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout);
    
    read ();
    solve ();
        
    return 0;
}