#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int n, m;
vector<pair<int, int> > vecini[200005];
bool viz[200005];
priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > > Q;
pair<int, int> sol[200005];
int nr = 0;
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({tmp3, tmp2});
vecini[tmp2].push_back({tmp3, tmp1});
}
}
void solve(){
Q.push({0, {0, 0}});
int s = 0;
while(!Q.empty()){
int d = Q.top().first;
int x = Q.top().second.first;
int y = Q.top().second.second;
Q.pop();
if(viz[x] == true){
continue;
}
sol[nr] = {x, y};
nr++;
viz[x] = true;
s += d;
int l = vecini[x].size();
for(int i = 0; i < l; i++){
if(viz[vecini[x][i].second] == false){
Q.push({vecini[x][i].first, {vecini[x][i].second, x}});
}
}
}
printf("%d\n%d\n", s, n - 1);
for(int i = 1; i < nr; i++){
printf("%d %d\n", sol[i].first + 1, sol[i].second + 1);
}
}
int main()
{
freopen("apm.in", "r", stdin);
freopen("apm.out", "w", stdout);
citire();
solve();
return 0;
}