#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <bitset>
#include <queue>
#include <cstring>

#define mp make_pair

using namespace std;

const int NMax = 200005;
const int inf = 0x3f3f3f3f;
bitset < NMax > viz;
int N, M;

struct muchie
{
    int m1,m2,c;
} v[NMax];

int GR[NMax], deep[NMax];

void Read()
{
    scanf("%d %d", &N, &M);
    for(int i=1; i<=M; ++i)
    {
        scanf("%d %d %d", &v[i].m1, &v[i].m2, &v[i].c);

    }

    for(int i=1; i<=N; ++i)
        GR[i] = i;
}

bool cmp(muchie a, muchie b)
{
    if(a.c < b.c)
        return true;
    return false;
}

int Find(int x)
{
    if(x != GR[x])
        GR[x] = Find(GR[x]);

    return GR[x];
}

void Join(int x, int y)
{
    if(deep[x] > deep[y])
    {
        GR[y] = x;
    }

    else
        if(deep[y] < deep[x])
    {
        GR[x] = y;
    }

    else
    {
        GR[x] = y;
        ++deep[y];
    }

}

void Solve()
{
    sort(v+1,v+M+1,cmp);

    int s = 0, muchii = 0;
    vector < pair < int, int > > rez;

    for(int i=1; i<=M; ++i)
    {
        if(Find(v[i].m1) != Find(v[i].m2))
        {
            Join(Find(v[i].m1),Find(v[i].m2));
            s+=v[i].c;
            ++muchii;
            rez.push_back(mp(v[i].m1,v[i].m2));
        }

        if(muchii == N-1)
            i=M+1;
    }

    printf("%d\n%d\n", s, N-1);

   vector < pair < int, int > > ::iterator it;

   for(it=rez.begin(); it!=rez.end(); ++it)
   {
       printf("%d %d\n", it->first, it->second);
   }

}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    Read();
    Solve();
    return 0;
}