#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
vector <pair <int, int>> v[200001];
bool viz[200001];
int c[200001];
int p[200001];
int main()
{
int n, m, i, j, x, y, z, nrsol;
int rasp;
fin >> n >> m;
for (i = 1; i<=m; i++)
{
fin >> x >> y >> z;
v[x].push_back ({y, z});
v[y].push_back ({x, z});
}
for (i = 1; i<=n; i++)
c[i] = 1000000000;
c[1] = 0;
viz[1] = 1;
for (i = 0; i<v[1].size(); i++)
{
c[v[1][i].first] = min (c[v[1][i].first], v[1][i].second);
p[v[1][i].first] = 1;
}
rasp = 0;
for (i = 1; i<=n-1; i++)
{
x = 0;
y = 1000000000;
for (j = 1; j<=n; j++)
if (viz[j] == 0)
{
if (c[j] < y)
{
x = j;
y = c[j];
}
}
viz[x] = 1;
rasp = rasp + y;
for (j = 0; j<v[x].size(); j++)
if (viz[v[x][j].first] == 0)
{
if (v[x][j].second < c[v[x][j].first])
{
c[v[x][j].first] = v[x][j].second;
p[v[x][j].first] = x;
}
}
}
fout << rasp << '\n';
fout << n-1 << '\n';
for (i = 2; i<=n; i++)
fout << i << ' ' << p[i] << '\n';
return 0;
}