#include <stdio.h>
#include <algorithm>

using namespace std;

char buff[2000];
int pos;
FILE*f=freopen("apm.in","r",stdin);
FILE*g=freopen("apm.out","w",stdout);

inline void read(int &nr)
{

    int semn;
    while((buff[pos] < '0' || buff[pos] > '9') && buff[pos]!='-') if(++pos == 2000) fread(buff, 1, 2000, stdin), pos = 0;
    nr = 0;
    if(buff[pos]=='-')
    {
        semn=-1;
        if(++pos == 2000) fread(buff, 1, 2000, stdin), pos = 0;

    }
    else semn=1;
    while('0' <= buff[pos] && buff[pos] <= '9')
    {
        nr = nr * 10 + buff[pos] - '0';
        if(++pos == 2000) fread(buff, 1, 2000, stdin), pos = 0;
    }
    nr*=semn;
}
int v[200001]= {0};
int dad[200001]= {0};

struct arcu
{
    int a, b, cost;
} arc[400001]= {0};

bool cmp(arcu a1, arcu a2)
{
    return (a1.cost<a2.cost);
}

int find_dad(int nod)
{

    if(dad[nod]==0)
        return nod;
    return find_dad(dad[nod]);
}

int main()
{
    int i, j, n, m, op, a, b, ta, tb, cost=0, lg=0;
    fread(buff, 1, 2000, stdin);
    read(n);
    read(m);
    for(i=1; i<=m; i++)
    {

        read(arc[i].a);
        read(arc[i].b);
        read(arc[i].cost);
    }
    sort(arc+1, arc+1+m, cmp);
    for(i=1; i<=m; i++)
    {
        ta=find_dad(arc[i].a);
        tb=find_dad(arc[i].b);
        if(ta!=tb)
        {
            cost+=arc[i].cost;
            v[++lg]=i;
            dad[ta]=tb;
            if(lg>=(n-1))
                break;
        }
    }

    printf("%d\n%d", cost, lg);
    for(i=1; i<lg; i++)
    {
        printf("%d %d\n", arc[v[i]].a, arc[v[i]].b);
    }
}