#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, i, x, y, z, s;
bool viz[200005];
vector<pair<int, int>>v[200005], r;
priority_queue<pair<int, pair<int, int>>>q;
int main()
{
    fin>>n>>m;
    for (i=1; i<=m; i++) {
        fin>>x>>y>>z;
        v[x].push_back({y, z});
        v[y].push_back({x, z});
    }
    viz[1]=1;
    for (auto x:v[1]) {
        q.push({-x.second, {x.first, 1}});
    }
    for (i=1; i<=n-1; i++) {
        auto x=q.top();
        q.pop();
        if (viz[x.second.first]==1) {i--; continue;}
        r.push_back(x.second);
        viz[x.second.first]=1;
        s-=x.first;
        for (auto y:v[x.second.first]) {
            if (viz[y.first]==0) q.push({-y.second, {y.first, x.second.first}});
        }
    }
    fout<<s<<'\n'<<n-1<<'\n';
    for (auto x:r) fout<<x.first<<' '<<x.second<<'\n';
    return 0;
}