#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int inf = 1000000;
int n, m;
vector<pair<int, int> > vecini[200005];
bool viz[200005];
int cost[200005];
int tata[200005];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pk;
void citire(){
scanf("%d %d", &n, &m);
int tmp1, tmp2, tmp3;
for(int i = 0; i < m; i++){
scanf("%d %d %d", &tmp1, &tmp2, &tmp3);
tmp1--;
tmp2--;
vecini[tmp1].push_back(make_pair(tmp3, tmp2));
vecini[tmp2].push_back(make_pair(tmp3, tmp1));
}
for(int i = 0; i <= n + 1; i++){
cost[i] = inf;
}
}
void solve(){
pk.push(make_pair(0, 0));
int nr = 0;
int sol = 0;
vector<pair<int, int> > solutii;
cost[0] = 0;
while(pk.empty() == false){
if(viz[pk.top().second] == true){
pk.pop();
continue;
}
sol += pk.top().first;
int nodCurent = pk.top().second;
pk.pop();
viz[nodCurent] = true;
int l = vecini[nodCurent].size();
for(int i = 0; i < l; i++){
if(viz[vecini[nodCurent][i].second] == false && cost[vecini[nodCurent][i].second] > vecini[nodCurent][i].first){
pk.push(vecini[nodCurent][i]);
tata[vecini[nodCurent][i].second] = nodCurent;
cost[vecini[nodCurent][i].second] = vecini[nodCurent][i].first;
}
}
}
printf("%d", sol);
printf("\n%d\n", n - 1);
for(int i = 1; i < n; i++){
printf("%d %d\n", i + 1, tata[i] + 1);
}
}
int main() {
freopen("apm.in", "r", stdin);
freopen("apm.out", "w", stdout);
citire();
solve();
return 0;
}