#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define pii pair <int, int>
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define NMAX 200005
using namespace std;
int n, m, best[NMAX], who[NMAX], res;
vector <pii> A[NMAX];
bool taken[NMAX], reachable[NMAX];
priority_queue <pii> Q;

void process(int node)
{
    taken[node] = true;
    int i, x, c;
    for (i = 0; i < (int)A[node].size(); i++)
    {
        x = A[node][i].x; c = A[node][i].y;
        if (!taken[x] && (best[x] > c || !reachable[x]))
            best[x] = c, who[x] = node, Q.push(mp(-c, x)), reachable[x] = true;
    }
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d%d", &n, &m);
    int i, x, y, z;
    for (i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &x, &y, &z);
        A[x].pb(mp(y, z)), A[y].pb(mp(x, z));
    }
    
    process(1);
    while (!Q.empty())
    {
        x = -Q.top().x; y = Q.top().y;
        Q.pop();
        if (!taken[y])
            process(y), res += x;
    }
    
    printf("%d\n%d\n", res, n - 1);
    for (i = 2; i <= n; i++)
        printf("%d %d\n", who[i], i);
    return 0;
}