#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define maxN 2000002
#define inf 2000000000
using namespace std;
int n, N, i, j, m, sol, cost[maxN], nre, t[maxN], r, minv, poz[maxN];
bool used[maxN];
int H[maxN * 2];
inline int father(int nod) {
    return nod / 2;
}

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

inline int right_son(int nod) {
    return nod * 2 + 1;
}
struct edge
{
    int x;
    int y;
}e[maxN];
void sift(int N, int K) {
    int son;
    do {
        son = 0;
        if (left_son(K) <= N) {
            son = left_son(K);
            if (right_son(K) <= N && cost[H[right_son(K)]] < cost[H[left_son(K)]]) {
                son = right_son(K);
            }
            if (cost[H[son]] >= cost[H[K]]) {
                son = 0;
            }
        }

        if (son) {
            swap(poz[H[K]], poz[H[son]]);
            swap(H[K], H[son]);
            K = son;
        }
    } while (son);
}
void percolate(int N, int K) {
    int key = H[K];

    while ((K > 1) && (cost[key] < cost[H[father(K)]])) {
        H[K] = H[father(K)];
        poz[H[father(K)]] = K;
        K = father(K);
    }

    H[K] = key;
    poz[key] = K;
}
void cut(int& N, int K) {
    if (N == K)
    {
        poz[H[K]] = 0;
        -- N;
        return ;
    }
    H[K] = H[N];
    poz[H[N]] = K;
    --N;

    if ((K > 1) && (cost[H[K]] < cost[H[father(K)]])) {
        percolate(N, K);
    } else {
        sift(N, K);
    }
}
void insert(int& N, int key) {
    H[++N] = key;
    poz[key] = N;
    percolate(N, N);
}
vector < pair < int, int > > V[maxN];
void read()
{
    int x, y, z;
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d %d", &n, &m);
    minv = inf;
    for (i = 1; i <= m; ++ i)
    {
        scanf("%d %d %d", &x, &y, &z);
        if (z < minv)
            minv = z,
                   r = x;
        V[x].push_back(make_pair(y, z));
        V[y].push_back(make_pair(x, z));
    }
}
void solve()
{
    int x, node;
    r = 1; N = 0;
    for (i = 1; i <= n; ++ i)
    {
        if (i != r)
           cost[i] = inf;
    }
    insert(N, 1);
    while (N)
    {
        x = H[1];

        cut(N, 1);
        poz[x] = 0;
        if (nre == n)
            break;

        used[x] = 1;
        sol += cost[x];
        e[++ nre].x = t[x];
        e[nre].y = x;
        for (i = 0; i < V[x].size(); ++ i)
        {
            node = V[x][i].first;
            if (!used[node] && V[x][i].second < cost[node])
            {
                t[node] = x;
                cost[node] = V[x][i].second;
                if (poz[node])
                    cut(N, poz[node]);

                insert(N, node);
            }
        }
    }
}
void write()
{
    freopen("apm.out", "w", stdout);
    printf("%d\n%d\n", sol, nre - 1);
    for (i = 2; i <= nre; ++ i)
        printf("%d %d\n", e[i].x, e[i].y);
}
int main()
{
    read();
    solve();
    write();
}