#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector<pair<int, int>> L[200001];
int d[200001];
int p[200001];
int viz[200001];
int main()
{
int n, m;
fin >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y, c;
fin >> x >> y >> c;
L[x].push_back({y, c});
L[y].push_back({x, c});
}
for(int i = 1; i <= n; i++)
{
d[i] = 1e9;
}
d[1] = 0;
int apm = 0;
priority_queue<pair<int, int>> pq;
pq.push({-d[1], 1});
while(pq.empty() == false)
{
int nod = pq.top().second;
int cost_curent = -pq.top().first;
pq.pop();
if(viz[nod] == 1)
continue;
viz[nod] = 1;
apm += cost_curent;
for(auto it : L[nod])
{
int vec = it.first;
int cost = it.second;
if(viz[vec] == 0 && d[vec] > cost)
{
d[vec] = cost;
p[vec] = nod;
pq.push({-d[vec], vec});
}
}
}
fout << apm << "\n";
fout << n - 1 << "\n";
for(int i = 2; i <= n; i++)
{
fout << i << " " << p[i] << "\n";
}
return 0;
}