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


using namespace std;
int n, m;

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

int graf[200005], adancime[200005];
int ok[200005];

void citeste()
{
    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)
        graf[i] = i;
}

int comparare(muchie x,muchie y)
{
    if(x.c<y.c)
        return 1;
    return 0;
}
int gaseste(int x)
{
    if(x != graf[x])
        graf[x] = gaseste(graf[x]);
    return graf[x];
}

void join(int x, int y)
{
    if(adancime[x] > adancime[y])
    {
        graf[y] = x;
    }
    else
        if(adancime[y] < adancime[x])
    {
        graf[x] = y;
    }
    else
    {
        graf[x] = y;
        ++adancime[y];
    }
}
void cerinta()
{
    sort(v+1,v+m+1,comparare);
    int s = 0, muchii = 0;
    vector < pair < int, int > > rez;
    for(int i=1; i<=m; ++i)
    {
        if(gaseste(v[i].m1) != gaseste(v[i].m2))
        {
            join(gaseste(v[i].m1),gaseste(v[i].m2));
            s+=v[i].c;
            ++muchii;
            rez.push_back(make_pair(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);
    citeste();
    cerinta();
    return 0;
}