#include<cstdio>
#include<algorithm>

using namespace std;

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

struct Edge
{
    int x,y,c;

    void initialize(int _x,int _y,int _c)
    {
        x = _x;
        y = _y;
        c = _c;
    }

    bool operator()(const Edge &A,const Edge &B)
    {
        return A.c < B.c;
    }
};

void Read(),Krushkal(),Print();

int N,M,Sol_cost;
Edge E[MMAX];
int Sol_edges[NMAX];

int Root[NMAX];
int Rang[NMAX];

int Find(int x)
{
    if(Root[x] != x) Root[x] = Find(Root[x]);
    return Root[x];
}

void Union(int x,int y)
{
    if(Rang[x] < Rang[y])
    {
        Root[x] = y;
        return;
    }
    if(Rang[x] > Rang[y])
    {
        Root[y] = x;
        return;
    }
    Root[x] = y;
    Rang[y]++;
}

int main()
{
    Read();
    Krushkal();
    Print();

    return 0;
}

void Read()
{
    int i,x,y,c;

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

    scanf("%d%d",&N,&M);

    for(i = 1; i <= M; i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        E[i].initialize(x,y,c);
    }
}

void Krushkal()
{
    int i,j,x,y,c;

    sort(E+1,E+M+1,Edge());

    for(i = 1; i <= N; i++)
        Root[i] = i;

    for(i = 1, j =0 ; i <= M && j <= N-1; i++)
    {
        x = E[i].x;
        y = E[i].y;
        c = E[i].c;

        if(Find(x) == Find(y)) continue;

        Union(Find(x),Find(y));
        Sol_cost += c;
        Sol_edges[++j] = i;
    }
}

void Print()
{
    int i;

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

    for(i = 1; i <= N-1; i++)
        printf("%d %d\n",E[Sol_edges[i]].x,E[Sol_edges[i]].y);
}