#include <bits/stdc++.h>

using namespace std;

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


int n,m,a,b,cost,d[200005],suma,mark[200005],tata[200005];
vector <pair<int,int>> v[200005];
priority_queue <pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;


void prim(){
    while (!pq.empty()){
        int cost = pq.top().first;
        int nod = pq.top().second;
        pq.pop();

        if (!mark[nod])
            mark[nod] = 1;

        for (int i = 0; i < v[nod].size(); i++){
            if (v[nod][i].second < d[v[nod][i].first] && !mark[v[nod][i].first]){
                 d[v[nod][i].first] = v[nod][i].second;
                 pq.push({d[v[nod][i].first], v[nod][i].first});
                 tata[v[nod][i].first] = nod;
            }
        }
    }

}


int main()
{
fin>>n>>m;
for (int i = 1; i <= m; i++){
    fin>>a>>b>>cost;
    v[a].push_back({b, cost});
    v[b].push_back({a, cost});
}
for (int i = 1; i <= n; i++){
    d[i] = 999999999;
}
d[1] = 0;
pq.push({0, 1});
prim();
for (int i = 1; i <= n; i++){
    suma += d[i];
}
fout << suma << '\n';
fout << n - 1 << '\n';
for (int i = 2; i <= n; i++){
    fout << i << " " << tata[i] << '\n';
}

return 0;
}