#include <bits/stdc++.h>

using namespace std;

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

int n, m;
int st, dr, c;
vector<pair<int,int>> v[200001];
int mark[200001], tata[200001];
bool visited[200001];

void prim(int start){
    mark[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, start});
    while(!pq.empty()){
        int cost_curr = pq.top().first;
        int nod_curr = pq.top().second;
        pq.pop();
        if (cost_curr != mark[nod_curr])
            continue;
        for (int i = 0; i < v[nod_curr].size(); i++){
            int vecin = v[nod_curr][i].first;
            int cost = v[nod_curr][i].second;
            if (cost < mark[vecin] && visited[vecin] == 0){
                tata[vecin] = nod_curr;
                mark[vecin] = cost;
                pq.push({mark[vecin], vecin});
            }
        }
        visited[nod_curr] = 1;
    }
}

int main(){
fin>>n>>m;
for (int i = 1; i <= m; i++){
    fin>>st>>dr>>c;
    v[st].push_back({dr, c});
    v[dr].push_back({st, c});
}
for (int i = 1; i <= n; i++){
    mark[i] = 999999999;
}
prim(1);
int total = 0;
for (int i = 2; i <= n; i++){
    total += mark[i];
}
fout << total << "\n";
fout <<  n - 1 << "\n";
for (int i = 2; i <= n; i++){
    fout << i << " " << tata[i] << "\n";
}
// complexitate O(mlogn)
    return 0;
}