#include <bits/stdc++.h>
#define Nmax 200005
#define pi pair<int, int>
#define mp make_pair
#define pb push_back
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int N, M, ans;
vector <pi> G[Nmax];
int x1[Nmax], x2[Nmax], nr[Nmax];
priority_queue<pi, vector<pi>, greater<pi> > Q;
pi apm[Nmax];
bool vis[Nmax];
int main()
{
    f >> N >> M;
    for (int i = 1; i <= M; ++i) {
        int x, y, d;
        f >> x >> y >> d;
        G[x].pb(mp(d, i));
        G[y].pb(mp(d, i));
        if (x == 1  || y == 1) Q.push(mp(d, i)), vis[i] = 1;
        x1[i] = x, x2[i] = y;
    }

    nr[1] = 1;
    int curr = 0;
    while (!Q.empty()) {
        int dist = Q.top().first, i = Q.top().second;
        int node = x1[i], node2 = x2[i];
        Q.pop();

     if (nr[node] == 0 || nr[node2] == 0)   {
        ++curr;
        ++nr[node], ++nr[node2];
        ans += dist;
        apm[curr].first = node, apm[curr].second = node2;
        if (nr[node2] == 1) node = node2;

        for (auto it: G[node])
            if (!vis[it.second]) Q.push(mp(it.first, it.second));
      }
    }

    g << ans << '\n' << N - 1 << '\n';
    for (int i = 1; i < N; ++i)
        g << apm[i].first << " " << apm[i].second << '\n';

    return 0;
}