#include <fstream>
#include <queue>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct vecin{
    int nod;
    int cost;
};
struct muchie{
    int a;
    int b;
    int cost;
    bool operator < (const muchie other) const {
        return cost > other.cost;
    }
};
priority_queue<muchie> p;
vector<vecin> v[int(2e5) + 5];
bool in[int(2e5) + 5];
int main(){
    vector<muchie> muchii_ans;
    int cost_total = 0;
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; i++){
        muchie m;
        fin >> m.a >> m.b >> m.cost;
        v[m.a].push_back({m.b, m.cost});
        v[m.b].push_back({m.a, m.cost});
    }
    for (int i = 0; i < v[1].size(); i++){
        p.push({1, v[1][i].nod, v[1][i].cost});
    }
    in[1] = true;
    while (!p.empty()) {
        muchie frn = p.top();
        p.pop();
        cost_total += frn.cost;
        muchii_ans.push_back(frn);
        in[frn.b] = true;
        for (int i = 0; i < v[frn.b].size(); i++){
            p.push({frn.b, v[frn.b][i].nod, v[frn.b][i].cost});
        }
        while (!p.empty() && in[p.top().b]){
            p.pop();
        }
    }
    fout << cost_total << '\n' << muchii_ans.size() << '\n';
    for (int i = 0; i < muchii_ans.size(); i++){
        fout << muchii_ans[i].a << " " << muchii_ans[i].b << '\n';
    }
    return 0;
}