#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>
#define mp make_pair
using namespace std;
int i, j, cost, x, y, N, M, Total, T[200100], Rank[200100];
vector< pair<int, int> > Sol;
vector< pair<int, int> >::iterator it;
set < pair<int, pair<int, int> > > H;
int TataLor(int x)
{
if (T[x]!=x) T[x]=TataLor(T[x]);
return T[x];
}
void FamilyReunion(int x, int y)
{
if ( Rank[x]<Rank[y] )
T[x]=y;
else T[y]=x;
if (Rank[x]==Rank[y]) Rank[x]++;
}
int main()
{
freopen("apm.in", "r", stdin);
freopen("apm.out", "w", stdout);
scanf("%d%d", &N, &M);
for (i=1; i<=N; i++)
for (j=1; j<=M; j++)
{
scanf("%d%d%d", &x, &y, &cost);
H.insert(mp(cost, mp(x,y) ) );
}
for (i=1; i<=N; i++) T[i]=i, Rank[i]=0;
while (! H.empty() )
{
pair< int,pair<int,int> > X=*(H.begin());
int Cost=X.first, A=(X.second).first, B=(X.second).second, tA=TataLor(A), tB=TataLor(B);
H.erase(H.begin());
if (tA!=tB)
{
Sol.push_back(mp(A,B));
Total+=Cost;
FamilyReunion(tA,tB);
}
}
printf("%d\n%d\n", Total, Sol.size());
for (it=Sol.begin(); it!=Sol.end(); it++)
printf("%d %d\n", (*it).first, (*it).second );
return 0;
}