#include <bits/stdc++.h>

#define ll long long

//#define fin cin
//#define fout cout

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

vector <pair<int, int>> g[200005];
stack <pair<int, int>> gl[200005];
vector <int> in_apm;
vector <int> muchii_inapm[200005];
bitset<200005> in_apm_bool;

int main()
{
    fin.tie(0); fin.sync_with_stdio(false);
    int n, m, x, y, c;
    fin>>n>>m;
    for (int i=1; i<=m; i++) {
        fin>>x>>y>>c;
        g[x].push_back({c, y});
        g[y].push_back({c, x});
    }
    for (int i=1; i<=n; i++) {
        sort (g[i].begin(), g[i].end(), greater<pair<int, int>>());
        for (pair<int, int> elem : g[i]) {
            gl[i].push(elem);
        }
        g[i].clear();
        g[i].shrink_to_fit();
    }
    in_apm.push_back(1);
    in_apm_bool[1]=1;
    int cost=0;
    for (int t=1; t<=n-1; t++) {
        pair<int, int> best_muchie={INT_MAX, INT_MAX};
        int from_nod;
        for (int i=0; i<in_apm.size(); i++) {
            int nod=in_apm[i];
            while (gl[nod].size()>0&&in_apm_bool[gl[nod].top().second]==1) {
                gl[nod].pop();
            }
            if (gl[nod].size()>0&&gl[nod].top().first<best_muchie.first&&in_apm_bool[gl[nod].top().second]==0) {
                best_muchie.first=gl[nod].top().first;
                best_muchie.second=gl[nod].top().second;
                from_nod=nod;
            }
        }
        muchii_inapm[from_nod].push_back(best_muchie.second);
        in_apm_bool[best_muchie.second]=1;
        in_apm.push_back(best_muchie.second);
        cost+=best_muchie.first;
    }
    fout<<cost<<'\n'<<n-1<<'\n';
    for (int i=1; i<=n; i++) {
        for (int vecin : muchii_inapm[i]) {
            fout<<i<<' '<<vecin<<'\n';
        }
    }
    return 0;
}