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

#define mp make_pair
#define pb push_back

using namespace std;

const int NMax = 200005;
const int MMax = 400005;

int N, M, sum;
int deep[NMax], dad[NMax];

vector < pair < int, int > > rez;

struct muchie
{
    int x, y, c;
}G[MMax];

bool cmp(muchie a, muchie b)
{
    if(a.c < b.c)
        return 1;

    return 0;
}

void Read()
{
    scanf("%d%d", &N, &M);

    for(int i=1; i<=M; ++i)
    {
        int x,y,c;

        scanf("%d%d%d", &G[i].x, &G[i].y, &G[i].c);
        dad[i]=i;

    }
}

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

    return dad[x];
}

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

    else
        dad[x] = y;

    if(deep[x]==deep[y])
        deep[y]++;
}

void Kruskal()
{
    sort(G+1, G+M+1, cmp);
    int sol=1;

   for(int i=1; i<=M; ++i)
   {
       if(Find(G[i].x) != Find(G[i].y) && sol<=N-1)
       {
           ++sol;
           sum += G[i].c;
           Join(Find(G[i].x), Find(G[i].y));
           rez.push_back(make_pair(G[i].x, G[i].y));
       }
   }

   printf("%d\n", sum);
   printf("%d\n", 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();
    Kruskal();
    return 0;
}