#include<cstdio>
#include<queue>

using namespace std;

const int NMAX = 200000;
const int MMAX = 400000;

struct str
{
    int l;
    int r;
    int c;
    int id;

} vert[1 + MMAX];

bool operator<(const str& a, const str& b)
{
  return a.c > b.c;
}

priority_queue<str> heap;

int n, m;
int tata[1 + NMAX];
int sz[1 + NMAX];
int res[1 + NMAX];
int res_ct;
int sum;

int ma(int a, int b)
{
    if(a > b)
    {
        return a;
    }
    return b;
}

int are_joined(int nod1, int nod2)
{
    int tata1 = nod1;
    while(tata[tata1] != tata1)
    {
        tata1 = tata[tata1];
    }

    int tata2 = nod2;
    while(tata[tata2] != tata2)
    {
        tata2 = tata[tata2];
    }

    //printf("1: %d %d   2: %d %d\n", nod1, tata1, nod2, tata2);
    if(tata1 == tata2)
    {
        return 1;
    }
    return 0;
}

void join(int nod1, int nod2)
{
    int tata1 = nod1;
    while(tata[tata1] != tata1)
    {
        tata1 = tata[tata1];
    }

    int tata2 = nod2;
    while(tata[tata2] != tata2)
    {
        tata2 = tata[tata2];
    }

    if(sz[tata1] >= sz[tata2])
    {
        sz[tata1] = ma(sz[tata1], sz[tata2] + 1);
        tata[tata2] = tata1;

        int temp;
        tata2 = nod2;
        while(tata[tata2] != tata2)
        {
            temp = tata[tata2];
            tata[tata2] = tata1;
            tata2 = temp;
        }
    }
    else
    {
        sz[tata2] = ma(sz[tata2], sz[tata1] + 1);
        tata[tata2] = tata1;

        int temp;
        tata1 = nod1;
        while(tata[tata1] != tata1)
        {
            temp = tata[tata1];
            tata[tata1] = tata2;
            tata1 = temp;
        }
    }
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    scanf("%d %d", &n, &m);

    for(int i = 1; i <= n; i++)
    {
        tata[i] = i;
        sz[i] = 1;
    }

    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d %d", &vert[i].l, &vert[i].r, &vert[i].c);
        vert[i].id = i;

        heap.push(vert[i]);
    }

    while(!heap.empty())
    {
        //printf("%d\n", (heap.top()).c);
        if(are_joined((heap.top()).l, (heap.top()).r) == 0)
        {
            join((heap.top()).l, (heap.top()).r);

            sum += (heap.top()).c;
            res_ct++;
            res[res_ct] = (heap.top()).id;
        }

        heap.pop();
    }

    printf("%d\n", sum);
    printf("%d\n", res_ct);
    for(int i = 1; i <= res_ct; i++)
    {
        printf("%d %d\n", vert[res[i]].l, vert[res[i]].r);
    }
}