#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

struct muchie
{
    //Priority Queue sortat crescator
    int cost, dir, home;
    bool operator<(const muchie &y) const { return cost > y.cost; }
    bool operator>(const muchie &y) const { return cost < y.cost; }
};

#define MAX_N 200001

vector <muchie> graf[MAX_N];

bool viz[MAX_N];

priority_queue<muchie> Q;

struct ptAns
{
    int a, b;
};
vector <ptAns> v;

int main()
{
    int n, m, x, y, c, ans = 0;
    in >> n >> m;
    for(int i = 0; i < m; ++i) {
        in >> x >> y >> c;
        graf[x].push_back({c, y, x});
        graf[y].push_back({c, x, y});
    }

    viz[1] = 1;
    for(auto x : graf[1]) { //Punem in coada muchiile accesibile din radacina (nodul 1);
        Q.push(x);
    }
    for(int i = 1; i < n; ++i)  {
        //la fiecare pas luam cate o muchie noua, dupa ce le stergem pe cele inutile
        while(viz[Q.top().dir]) {
            Q.pop();
        }
        auto it=Q.top();

        v.push_back({it.home, it.dir});
        viz[it.dir] = 1;
        for(auto x : graf[it.dir]) { //Adaugam muchiile accesibile din noul nod adaugat in APM
            if(!viz[x.dir])
                Q.push(x);
        }
        ans += it.cost;
    }
    out << ans << '\n' << v.size() << '\n';
    for(auto x : v) {
        out << x.a << " " << x.b << '\n';
    }
    return 0;
}