#include <vector>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
struct muchie {
    int u, v, w;
};
class mycomparison
{
public:
  bool operator() (const muchie& lhs, const muchie&rhs) const
  {
        return (lhs.w > rhs.w);
  }
};
#define NMAX 200010
class Task {
public:
    void solve() {
        read_input();
        get_result();
        print_output();
    }

private:

    int n, m, apm;

    vector<int> viz;
    vector<pair<int, int> > sol;
    vector<pair<int, int> > adj[NMAX];
    priority_queue<muchie,vector<muchie>,mycomparison> pq;
    void read_input() {
        cin >> n >> m;

        for(int i = 1; i <= m; ++i) {
            int x, y, c;
            cin >> x >> y >> c;
            adj[x].push_back({y, c});
            adj[y].push_back({x, c});
        }
    }

    void get_result() {
        Prim();
    }

    void Prim() {
        apm = 0;
        viz.clear();
        viz.resize(n + 1, 0);
        viz[1] = 1;
        for(unsigned i = 0; i < adj[1].size(); ++i) {
            pq.push({1, adj[1][i].first, adj[1][i].second});
        }
        while(!pq.empty()) {
            int nod = pq.top().u;
            int fiu = pq.top().v;
            int cost = pq.top().w;
            pq.pop();
            if(viz[fiu] == 1) continue;
            apm += cost;
            sol.push_back({nod, fiu});
            viz[fiu] = 1;
            for(unsigned i = 0; i < adj[fiu].size(); ++i) {
                int vecin = adj[fiu][i].first;
                int w = adj[fiu][i].second;
                if(viz[vecin] == 0) {
                    pq.push({fiu, vecin, w});
                }
            }
        }
    }

    void print_output() {
        cout << apm << '\n';
        cout << n - 1 << '\n';
        for (int i = 0; i < n - 1; ++i) {
            cout << sol[i].first << ' ' << sol[i].second << '\n';
        }
    }
};

int main() {
    // din cauza ca fac redirectari, salvez starea lui cin si cout
    auto cin_buff = cin.rdbuf();
    auto cout_buff = cout.rdbuf();

    // las liniile urmatoare daca citesc din fisier
    ifstream fin("apm.in");
    cin.rdbuf(fin.rdbuf()); // save and redirect

    // las liniile urmatoare daca afisez in fisier
    ofstream fout("apm.out");
    cout.rdbuf(fout.rdbuf()); // save and redirect

    // aici este rezolvarea propriu-zisa
    Task *task = new Task();
    task->solve();
    delete task;

    // restore pentru cin si cout
    cin.rdbuf(cin_buff);
    cout.rdbuf(cout_buff);

    // obs. nu e nevoie sa inchid fisierele
    // cand se apeleaza destructorii pentru fin si fout se vor inchide

    return 0;
}