#include <fstream>
#include <vector>


using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct elem
{
    int x,y,c;
}el,h[400003],el1,sol[200003];

vector <elem> G[200003];

int k=0,nr,n,m,sum;
bool viz[200003];

void adauga(elem val)
{
    h[++k]=val;
    int poz=k;
    while(h[poz].c<h[poz/2].c&&poz/2>0)
    {
        swap(h[poz],h[poz/2]);
        poz/=2;
    }
}

void elimina()
{
    h[1]=h[k];
    k--;
    int poz=1;
    while(2*poz<=k)
    {
        int fiu;
        if(2*poz+1<=k)
        {
            if(h[2*poz+1].c<h[2*poz].c)
                fiu=2*poz+1;
            else
                fiu=2*poz;
        }
        else
            fiu=2*poz;
        if(h[poz].c<h[fiu].c)
            return;
        else
        {
            swap(h[poz],h[fiu]);
            poz=fiu;
        }
    }
}


void apm()
{
    sum=0;
    el.x=0;
    el.y=1;
    el.c=0;
    adauga(el);
    while(k)
    {
        el=h[1];
        elimina();
        if(viz[el.y]==0)
        {
            sum+=el.c;
            sol[++nr]=el;
            viz[el.y]=1;
            for(vector <elem>::iterator it=G[el.y].begin();it!=G[el.y].end();it++)
            {
                if(viz[it->y]==0)
                {
                    el1.x=it->x;
                    el1.y=it->y;
                    el1.c=it->c;
                    adauga(el1);
                }
            }
        }
    }
}


int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        el.x=x;
        el.y=y;
        el.c=c;
        G[x].push_back(el);
        swap(el.x,el.y);
        G[y].push_back(el);
    }
    apm();
    fout<<sum<<"\n"<<nr-1<<"\n";
    for(int i=2;i<=nr;i++)
        fout<<sol[i].x<<" "<<sol[i].y<<"\n";
    return 0;
}