#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define maxN 200002
#define inf 2000000000
using namespace std;
int n, i, j, m, sol, cost[maxN], nre, t[maxN], r, minv;
bool used[maxN];
struct edge
{
    int x;
    int y;
}e[maxN];
struct comp
{
    bool operator() (const int &X, const int &Y)
    {
        return cost[X] > cost[Y];
    }
};
vector < pair < int, int > > V[maxN];
priority_queue < int, vector < int >, comp> q;
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;
    for (i = 1; i <= n; ++ i)
    {
        if (i != r)
           cost[i] = inf;
    }
    q.push(r);
    while (!q.empty())
    {
        x = q.top();
        q.pop();
        if (used[x])
            continue;
        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 (V[x][i].second < cost[node])
            {
                t[node] = x;
                cost[node] = V[x][i].second;
            }
            q.push(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();
}