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

using namespace std;

#define NMAX 200015

int N,M;
int APM_Kosten;

int Vater[NMAX];
int Tiefe[NMAX];

struct Rand{
    int Kosten, Knoten1, Knoten2;

    Rand(int x, int y, int z)
    {
        Knoten1 = x;
        Knoten2 = y;
        Kosten = z;
    }
};

vector < int > APM;
vector < Rand > Randen;

bool cmp(Rand i, Rand j)
{
    return i.Kosten < j.Kosten;
}

void Scannen()
{
    freopen("apm.in","r",stdin);

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

    for(int i=1,x,y,z;i<=M;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        Randen.push_back(Rand(x,y,z));
    }
}

int Die_Wurzel(int Knoten)
{
    if(Knoten == Vater[Knoten])
        return Knoten;
    return Die_Wurzel(Vater[Knoten]);
}

void Vereinen(int Knoten1, int Knoten2)
{
    int Wurzel1 = Die_Wurzel(Knoten1);
    int Wurzel2 = Die_Wurzel(Knoten2);

    if(Tiefe[Wurzel1] >= Tiefe[Wurzel2])
        Vater[Wurzel2] = Wurzel1;
    else
        Vater[Wurzel1] = Wurzel2;

    if(Tiefe[Wurzel1] == Tiefe[Wurzel2])
        Tiefe[Wurzel1]++;
}

bool SindBruder(int Knoten1, int Knoten2)
{
    return Die_Wurzel(Knoten1) == Die_Wurzel(Knoten2);
}

void Losen_Kruskal()
{
    for(int i=1;i<=N;i++)
        Vater[i] = i;

    sort(Randen.begin(),Randen.end(),cmp);

    for(unsigned i = 0; i < Randen.size(); i++)
    {
        if(SindBruder(Randen[i].Knoten1,Randen[i].Knoten2))
            continue;

        Vereinen(Randen[i].Knoten1,Randen[i].Knoten2);
        APM_Kosten += Randen[i].Kosten;
        APM.push_back(i);

        if(APM.size() >= N-1)
            return;
    }
}

void Drucken()
{
    freopen("apm.out","w",stdout);

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

    for(vector < int > :: iterator it = APM.begin(); it!=APM.end(); ++it)
        printf("%d %d\n",Randen[*it].Knoten1,Randen[*it].Knoten2);
}

int main()
{
    Scannen();
    Losen_Kruskal();
    Drucken();
    return 0;
}