#include <iostream>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <queue>
#define INF (1e7)
using namespace std;

ostream& operator<<(ostream& out, pair<int,int> &obj) {
    out << obj.first << ' ' << obj.second;
    return out;
}

void citire(int &n, int &m, vector<pair<int, int>> **G) {
    ifstream fin("apm.in");
    if(!fin.is_open()) {
        cout << "The file can't be opened!\n";
        exit(EXIT_FAILURE);
    }

    fin >> n >> m;
    *G = new vector<pair<int, int>>[n + 1];
    int x = 0, y = 0;
    int cost = 0;
    for(int i = 0 ; i < m; ++i) {
        fin >> x >> y >> cost;
        (*G)[x].push_back({y, cost});
        (*G)[y].push_back({x, cost});
    }

    fin.close();
}

void Prim(int n, int m, vector<pair<int, int>> *G) {
    auto d = new int[n + 1];
    auto tata = new int[n + 1];
    auto viz = new int[n + 1];
    vector<pair<int, int>> Edge;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int> > > Q;
    int costTotal = 0;

    for(int i = 1 ; i <= n ; ++i) {
        d[i] = INF;
        tata[i] = 0;
        viz[i] = 0;
    }
    d[1] = 0;
    Q.push({d[1], 1});

    while(!Q.empty()) {
        int u = Q.top().second;
        Q.pop();
        if(!viz[u]) {
            for (auto x : G[u]) {
                int v = x.first;
                int Wuv = x.second;
                if (viz[v] == 0 && Wuv < d[v]) {
                    d[v] = Wuv;
                    tata[v] = u;
                    Q.push({d[v], v});
                }
            }
            viz[u] = 1;
            if(u != 1) {
                costTotal += d[u];
                Edge.push_back({u, tata[u]});
            }
        }

    }

    ofstream fout("apm.out");
    fout << costTotal << '\n' << Edge.size() << '\n';
    for(auto x : Edge) {
        fout << x << '\n';
    }
    delete[] d;
    delete[] tata;
    delete[] viz;
}

int main() {
    int n, m;
    vector<pair<int, int>> *G;
    citire(n, m, &G);
    Prim(n, m, G);
    return 0;
}