#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, t[200004], d[200004], k, tx, ty, S;
pair<int, int> sol[400004];
vector<pair<int, int> > a[200004];
const int inf = 1 << 30;
priority_queue<pair<int, int> > pq;
bitset<200004> w;

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({y, c});
        a[y].push_back({x, c});
    }
    for(int i = 1; i <= n; ++ i) d[i] = inf;
    pq.push({0, 1});
    vector<pair<int, int> >  :: iterator it;
    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)
             if(d[(*it).f] > (*it).s && !w[(*it).f]) d[(*it).f] = (*it).s, t[(*it).f] = x, pq.push({-d[(*it).f], (*it).f});
    }
    for(int i = 1; i <= n; ++ i) if(d[i] != inf) S+= d[i], sol[++ k] = {i, t[i]};
    fprintf(G, "%d\n%d\n", S, n-1);
    for(int i = 1; i < n; ++ i)
        fprintf(G, "%d %d\n", sol[i].f, sol[i].s);
    return 0;
}