#include <iostream>
#include <fstream>
#include <vector>
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;
for(int i = 1; i <= n; i++)
{
int mn = 1e9;
int nod = 0;
for(int j = 1; j <= n; j++)
{
if(viz[j] == 0 && d[j] < mn)
{
mn = d[j];
nod = j;
}
}
apm += d[nod];
viz[nod] = 1;
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;
}
}
}
fout << apm << "\n";
fout << n - 1 << "\n";
for(int i = 2; i <= n; i++)
{
fout << i << " " << p[i] << "\n";
}
return 0;
}