#include <cstdio>
#include <vector>
#include <set>
#include <cstring>
#define pb push_back
#define mkp make_pair
#define SIZE 200001

using namespace std;

vector < pair <int, int> > adj[SIZE];
set < pair <int, int> > q;

int n, i, m, x, y, c, min_cost, node, node_dest, cost, remaining, parent[SIZE], dist[SIZE];
bool used[SIZE];

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d %d", &n, &m);

    while (m--)
    {
        scanf("%d %d %d", &x, &y, &c);
        adj[x].pb(mkp(y, c));
        adj[y].pb(mkp(x, c));
    }

    memset(dist, 0x3f3f3f3f, sizeof(dist));
    dist[1] = 0;
    remaining = n;

    q.insert( mkp(0, 1));

    while (remaining && !q.empty())
    {
        node = ( *q.begin() ).second;
        q.erase( q.begin() );
        if( used[node] )
            continue;
        min_cost += dist[node];
        --remaining;
        used[node] = 1;
        for(vector < pair <int, int> > :: iterator it= adj[node].begin(); it!=adj[node].end(); ++it)
        {
            node_dest = (*it).first;
            if( used[node_dest] )
                continue;
            cost = (*it).second;
            if(dist[node_dest] > cost)
            {
                dist[node_dest] = cost;
                parent[node_dest]=node;
                q.insert(mkp(cost, node_dest));
            }
        }

    }
    printf("%d\n%d\n", min_cost, n-1);

    for(i=2; i<=n; ++i)
        printf("%d %d\n", parent[i], i);
    return 0;
}