//ALGORITM KRUSKAL - DISJOINT SETS + UNION BY RANK + PATH COMPRESSION
#include <iostream>
#include <fstream>
#include <algorithm>
#define LN 200000
#define LM 400000
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

int n,m;
/*struct nod{
    int vecin;
    struct nod *urm;
}*L[LN+2];*/
struct muchie{
    int nod1,nod2,cost;
    bool apm;
}mch[LM+2];

int p[LN]; //vector parinti
int rang[LN]; //vectorul de ranguri

void create_set(int i)
{
    p[i]=i;
    rang[i]=0;
}
int find_set(int i)
{
    if(p[i] != i)
        p[i]=find_set(p[i]);
    return p[i];
}
bool merge_set(int a,int b)
{
    int aroot = find_set(a);
    int broot = find_set(b);

    if(aroot == broot)
        return 0;
    else
    {
        if(rang[aroot] > rang[broot])
            p[broot]=aroot;
        else if(rang[aroot] < rang[broot])
            p[aroot]=broot;
        else if(rang[aroot]==rang[broot])
        {
            p[broot]=aroot;
            rang[aroot]++;
        }
        return 1;
    }
}
bool compare(struct muchie a, struct muchie b)
{
    return a.cost < b.cost;
}

int main()
{
    int x,y,c;
    in>>n>>m;
    for(int i=1;i<=m;++i)
    {
        in>>x>>y>>c;

        /*p = new nod;
        p->vecin=x;
        p->urm=L[y];
        L[y]=p;

        p = new nod;
        p->vecin=y;
        p->urm=L[x];
        L[x]=p;*/

        mch[i].nod1 = x;
        mch[i].nod2 = y;
        mch[i].cost = c;
    }

    sort(mch+1,mch+m+1,compare);

    /*for(int i=1;i<=m;++i)
        out<<mch[i].nod1<<" "<<mch[i].nod2<<" "<<mch[i].cost<<"\n";
    out<<"\n";*/

    for(int i=1;i<=n;++i)
        create_set(i);

    int muchiiAPM=0;
    int costAPM=0;
    for(int i=1;i<=m && muchiiAPM<n-1;++i)
    {
        if(merge_set(mch[i].nod1, mch[i].nod2))
        {
            muchiiAPM++;
            mch[i].apm=1;
            costAPM+=mch[i].cost;
        }
    }

    out<<costAPM<<"\n"<<n-1<<"\n";
    for(int i=1;i<=m;++i)
        if(mch[i].apm)
            out<<mch[i].nod1<<" "<<mch[i].nod2<<"\n";

    return 0;
}