#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

int n,m,cost,conexe,much;

struct muchii
{
    int x,y,c;
    bool viz=false;
}s;
vector<muchii> T;
vector<int> comp;
vector<muchii>::iterator it;

bool cp(muchii a,muchii b)
{
    return a.c<b.c;
}

void citire()
{
    scanf("%d %d",&n,&m);
    int x,y,c;
    for(int i=1;i<m+1;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        s.x=x;s.y=y;s.c=c;
        T.push_back(s);
    }
    for(int i=1;i<n+1;i++)comp.push_back(i);
    sort(T.begin(),T.end(),cp);
}

void afisare()
{

    printf("%d \n",cost);
    printf("%d \n",much);
    for(it=T.begin();it!=T.end();it++)
        if(it->viz==true)
            printf("%d %d \n",it->x,it->y);
}

void UF(int mi,int ma)
{
    int i,ok=0;

    for(i=1;i<n+1;i++)
        if(comp[i]==ma){ok=1;
                comp[i]=mi;}

    it->viz=true;
    cost+=it->c;
    much++;
    if(ok==1)conexe--;
}

void krusk()
{

    for(it=T.begin();it!=T.end();it++){
        if(comp[it->x]!=comp[it->y])
            if(comp[it->x]<comp[it->y]) UF(comp[it->x],comp[it->y]);
                else UF(comp[it->y],comp[it->x]);
    if(conexe==1) break;
}
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    conexe=n;
    citire();
    krusk();
    afisare();

    return 0;
}