#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

FILE *F=fopen("apm.in", "r"), *G=fopen("apm.out", "w");

int n, m, x, y, c, Min, k, S, d[200003], t[200003];
vector<pair<int, int> > a[200003];
priority_queue<pair<int, int> > pq;
bitset<200005> w;
const int inf = 1 << 30;

int main()
{
    fscanf(F, "%d %d ", &n, &m);
    for(int i = 1; i <= m; ++ i)
        fscanf(F, "%d %d %d ", &x, &y, &c), a[x].push_back({c, y}), a[y].push_back({c, x});
    for(int i = 1; i <= n; ++ i)
        d[i] = inf;
    pq.push({0, 1});
    vector<pair<int, int> > :: iterator it;
    int z1, z2;
    while(!pq.empty())
    {
        x = pq.top().s;
        pq.pop();
        if(w[x]) continue;
        w[x] = 1;
        for(it = a[x].begin(); it != a[x].end(); ++ it)
        {
            z1 = (*it).f;
            z2 = (*it).s;
            if(d[z2] > z1 && !w[(*it).s])
                d[z2] = z1, pq.push({-d[z2], z2}), t[z2] = x;
        }
    }
    for(int i = 1; i <= n; ++ i)
        if(d[i] != inf)
            S += d[i];
    fprintf(G, "%d\n%d\n", S, n-1);
    for(int i = 2; i <= n; ++ i)
        fprintf(G, "%d %d\n", t[i], i);
    return 0;
}