#include <fstream>
#include <queue>
#include <vector>
using namespace std;
#define NMAX 200005
#define INF 5000000000
typedef pair<int, int> ii;

ifstream fin ("apm.in");
ofstream fout ("apm.out");
vector<ii> a[NMAX], sol;
int n, m, i, k, minim, x, y, z, total, key[NMAX], t[NMAX];
bool inmst[NMAX];

int main()
{
    fin >> n >> m;
    for(i=1; i<=m; i++) {
        fin >> x >> y >> z;
        a[x].push_back(ii(y, z));
        a[y].push_back(ii(x, z));
    }

    for(i=2; i<=n; i++)
        key[i] = INF;

    priority_queue <ii, vector<ii>, greater<ii> > pq;
    pq.push(ii(0, 1));

    while(!pq.empty()) {
        x = pq.top().second;
        z = pq.top().first;
        pq.pop();

        if(z > key[x] || inmst[x])
            continue;

        inmst[x] = true;
        total += key[x];
        if(x != 1)
            sol.push_back(ii(x, t[x]));
        for(i=0; i<(int)a[x].size(); i++) {
            y = a[x][i].first;
            z = a[x][i].second;
            if(key[y] > z && !inmst[y]) {
                pq.push(ii(z, y));
                key[y] = z;
                t[y] = x;
            }
        }
    }

    fout << total << endl << n-1 << endl;
    for(i=0; i<(int)sol.size(); i++)
        fout << sol[i].first << " " << sol[i].second << endl;

    return 0;
}