#include <bits/stdc++.h>

using namespace std;

const int NMAX = 2e5,INF = 2e9;
int dist[NMAX + 5],p[NMAX + 5];
bool viz[NMAX + 5];
vector <pair <int, int> > edges[NMAX + 5];
priority_queue <pair <int, int> > pq;

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n,m,a,b,c,d,ans = 0;
    fin >> n >> m;
    for (int i = 1;i <= n;i++)
        dist[i] = INF;
    for (int i = 0;i < m;i++) {
        fin >> a >> b >> c;
        edges[a].push_back({b, c});
        edges[b].push_back({a, c});
    }
    pq.push({0, 1});
    dist[1] = 0;
    while (!pq.empty()) {
        c = pq.top().first;
        a = pq.top().second;
        pq.pop();
        if (c != -dist[a])
            continue;
        viz[a] = 1;
        ans += -c;
        for (int i = 0;i < edges[a].size();i++) {
            b = edges[a][i].first;
            d = edges[a][i].second;
            if (!viz[b] && d < dist[b]) {
                dist[b] = d;
                p[b] = a;
                pq.push({-d, b});
            }
        }
    }
    fout << ans << '\n' << n - 1 << '\n';
    for (int i = 2;i <= n;i++)
        fout << i << " " << p[i] << '\n';
    return 0;
}