#include <fstream>
#include <vector>
#include <queue>
#define NMAX 200001
#define INF 4000001
using namespace std;

struct muchie {
    int from,to;
    int cost;
};

typedef vector<muchie> adiacente;
adiacente toateMuchiile[NMAX];
bool viz[NMAX];
int n, m;

class comparare{
    public:
    bool operator() (const muchie &a, const muchie &b){
        return a.cost > b.cost;
    }
};

priority_queue<muchie, vector<muchie>, comparare> heap;

int pondereArbore;
adiacente rezultat;


void prim(int);

int main() {
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    int x, y, c;
    for (int i = 1; i <= m; i++) {
        f>>x>>y>>c;
        muchie X;
        X.from = x;
        X.to = y;
        X.cost = c;
        toateMuchiile[x].push_back(X);

        muchie Y;
        Y.from = y;
        Y.to = x;
        Y.cost = c;
        toateMuchiile[y].push_back(Y);
    }

    prim(1);

    g<<pondereArbore<<'\n';
    g<<rezultat.size()<<'\n';
    for (adiacente::iterator i = rezultat.begin(); i != rezultat.end(); ++i) {
        g<<i->to<<' '<<i->from<<'\n';
    }

    return 0;
}

void prim(int start) {

    viz[start] = true;

    for (adiacente::iterator i = toateMuchiile[start].begin(); i != toateMuchiile[start].end(); ++i) {
        heap.push(*i);
    }
    while (!heap.empty()) {
        if(rezultat.size()==n-1)
            break;
        muchie top = heap.top();
        heap.pop();

        if (viz[top.to])
            continue;
        pondereArbore += top.cost;
        rezultat.push_back(top);
        viz[top.to] = true;
        for (adiacente::iterator i = toateMuchiile[top.to].begin(); i != toateMuchiile[top.to].end(); ++i) {
            if (!viz[i->to]) {
                heap.push(*i);
            }
        }
    }
}