#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)
{
    int Tx=TataLor(x) , Ty=TataLor(y);
    if ( Rank[Tx]<Rank[Ty] )
        T[Tx]=Ty;
    else T[Ty]=Tx;
    if (Rank[Tx]==Rank[Ty]) Rank[Tx]++;
}
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;
    for (i=1; i<=M; i++)
    {
        x=(*H.begin() ).second.first;
        y=(*H.begin() ).second.second;
        cost=(*H.begin() ).first;
        H.erase( H.begin() );
        if (TataLor(x)!=TataLor(y))
        {
            FamilyReunion(x,y);
            Total+=cost;
            Sol.push_back(mp(x,y));
        }
    }
    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;
}