#include <bits/stdc++.h>
#define MAX 131072

using namespace std;
const int EMAX = 400010;
const int NMAX = 200010;

FILE *IN;

struct edge{
    int x, y, cost;
}edges[EMAX];
struct aEdge{
    int x, y;
}ansEdges[EMAX];

int N, M;
int Cost, ans;
int comp[NMAX];

int pos, sign;
char f[MAX];

inline void Read(int &nr){
    sign = 0;
    nr = 0;
    while(f[pos] < '0' || f[pos] > '9'){
        if(f[pos] == '-') sign = 1;
        pos++;
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    while(f[pos] >= '0' && f[pos] <= '9'){
        nr = 10 * nr + f[pos++] - '0';
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    if(sign) nr =- nr;
}

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

void read(){
    Read(N); Read(M);
    int a, b, C;
    for(int i = 1; i <= M; i++){
        Read(a); Read(b); Read(C);
        edges[i] = {a, b, C};
    }
    for(int i = 1; i <= N; i++)
        comp[i] = i;
    sort(edges + 1, edges + M + 1, cmp);
}

inline int Find(int x){
    int root = x, aux;
    while(root != comp[root])
        root = comp[root];
    while(x != root){
        aux = comp[x];
        comp[x] = root;
        x = aux;
    }
    return x;
}

inline void Union(int x, int y){
    comp[x] = y;
}

int main(){

    IN = fopen("apm.in", "r");
    freopen("apm.out", "w", stdout);

    read();

    int x, y;
    for(int i = 1; i <= M; i++){
        x = Find(edges[i].x);
        y = Find(edges[i].y);
        if(x != y){
            Union(x, y);
            Cost += edges[i].cost;
            ans++;
            ansEdges[ans] = {edges[i].y, edges[i].x};
        }
    }

    printf("%d\n%d\n", Cost, ans);
    for(int i = 1; i <= ans; i++)
        printf("%d %d\n", ansEdges[i].x, ansEdges[i].y);

    return 0;
}