//#include <bits/stdc++.h>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
using namespace std;
//ifstream fin("apm.in");
//ofstream fout("apm.out");
int n,m,x,y,c,i,j,cost,cmin,xmin,ymin, is[200200];
set<int> s;
vector<pair<int,int>> v;
priority_queue<pair<int,pair<int,int>>> p;
vector<pair<int,int>> g[200001];
int main()
{
//ios_base::sync_with_stdio(false);
freopen("apm.in", "r", stdin);
freopen("apm.out", "w", stdout);
cost=1001;
scanf("%d %d", &n, &m);
for (i=1;i<=m;i++)
{
scanf("%d%d%d", &x, &y, &c);//fin>>x>>y>>c;
if (c<cost)
{
cost=c;
xmin=x;
ymin=y;
}
g[x].push_back(make_pair(y,-c));
g[y].push_back(make_pair(x,-c));
}
pair<int,pair<int,int>> l;
v.push_back(make_pair(xmin,ymin));
is[xmin] = 1;
is[ymin] = 1;
int nr = 2;
for (auto i: g[xmin])
p.push(make_pair(i.second, make_pair(i.first, xmin)));
for (auto i: g[ymin])
p.push(make_pair(i.second, make_pair(i.first, ymin)));
while (nr < n)
{
l=p.top();
p.pop();
if (is[l.second.first] == 0)
{
if (is[l.second.second] == 1)
{
for (auto i: g[l.second.first])
{
if (is[i.first] == 0)
p.push(make_pair(i.second, make_pair(i.first, l.second.first)));
}
v.push_back(make_pair(l.second.first, l.second.second));
is[l.second.first] = 1;
nr++;
cost-=l.first;
}
}
else if (is[l.second.second] == 0)
{
for (auto i: g[l.second.second])
{
if (is[i.first] == 0)
p.push(make_pair(i.second, make_pair(i.first, l.second.second)));
}
v.push_back(make_pair(l.second.first, l.second.second));
is[l.second.second] = 1;
nr++;
cost-=l.first;
}
}
printf("%d\n%d\n", cost, n-1);
for (auto i: v)
{
printf("%d %d\n", i.first, i.second);
}
printf("\n");
return 0;
}