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

const int MAX_N = 200002;
const int MAX_M = 400002;
const int INF = (1 << 30);

typedef int Heap[MAX_N];

int N, M, ans;
int p[MAX_N], pos[MAX_N], val[MAX_N], sol[MAX_N][2];
vector < pair < int, int > > v[MAX_N];
bool m[MAX_N];
Heap H;

inline int left_son(int k) {
    return 2*k;
}

inline int right_son(int k) {
    return 2*k+1;
}

inline int father(int k) {
    return k/2;
}

inline void sift(Heap H, int N, int K) {
    int son;
    do {
        son = 0;
        if(left_son(K) <= N) {
            son = left_son(K);
            if(right_son(K) <= N && val[H[right_son(K)]] < val[H[son]])
                son = right_son(K);
        }
        if(val[H[son]] >= val[H[K]])
            son = 0;
        if(son) {
            int temp = H[K];
            H[K] = H[son], H[son] = temp;
            pos[H[K]] = K, pos[H[son]] = son;
            K = son;
        }
    } while(son);
}

inline void percolate(Heap H, int N, int K) {
    int temp = H[K];
    while(K > 1 && val[temp] < val[H[father(K)]]) {
        H[K] = H[father(K)];
        pos[H[K]] = K;
        K = father(K);
    }
    H[K] = temp, pos[temp] = K;
}

inline void cut(Heap H, int &N, int K) {
    H[K] = H[N], --N;
    if(N+1 == K)
        return;
    pos[H[K]] = K;
    if(K > 1 && val[H[K]] < val[H[father(K)]])
        percolate(H, N, K);
    else sift(H, N, K);
}

int main() {
    ifstream f("apm.in");
    ofstream g("apm.out");

    f >> N >> M;
    for(int i = 1, x, y, c; i <= M; ++i) {
        f >> x >> y >> c;
        v[x].push_back(make_pair(y, c)), v[y].push_back(make_pair(x, c));
    }

    int Nr = 0;
    for(int i = 2; i <= N; ++i)
        H[++Nr] = i, pos[i] = Nr, val[i] = INF;
    m[1] = true;
    for(size_t j = 0; j < v[1].size(); ++j) {
        int y = v[1][j].first, c = v[1][j].second;
        if(c < val[y]) {
            val[y] = c, p[y] = 1;
            cut(H, Nr, pos[y]);
            H[++Nr] = y, pos[y] = Nr;
            if(val[y] < val[H[father(Nr)]])
                percolate(H, Nr, Nr);
        }
    }
    for(int i = 1; i < N; ++i) {
        sol[i][0] = H[1], sol[i][1] = p[H[1]];
        ans += val[H[1]];
        int x = H[1];
        m[x] = true;
        cut(H, Nr, 1);
        for(size_t j = 0; j < v[x].size(); ++j) {
            int y = v[x][j].first, c = v[x][j].second;
            if(c < val[y] && m[y] == false) {
                val[y] = c;
                p[y] = x;
                cut(H, Nr, pos[y]);
                H[++Nr] = y, pos[y] = Nr;
                if(val[y] < val[H[father(Nr)]])
                    percolate(H, Nr, Nr);
                }
        }
    }

    g << ans << '\n' << N-1 << '\n';
    for(int i = 1; i < N; ++i)
        g << sol[i][0] << ' ' << sol[i][1] << '\n';


    f.close();
    g.close();

    return 0;
}