#include <iostream>
#include <fstream>
#define maxN 200005
#define maxM 400005
#define inf 0x3f3f
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int n,m,nr_m_apm=0,apm[maxM][2],graf[maxM][4],c_total=0,tree[maxN],nr=0;

void read()
{
    int i,a,b,z;
    f>>n; f>>m;
    for(i=1; i<=m ;i++)
    {
        f>>a; f>>b; f>>z;
        graf[i][0]=a;
        graf[i][1]=b;
        graf[i][2]=z;
        graf[i][3]=0;
    }
    for(i=1; i<=n ;i++)
        tree[i]=i;
}

void new_m(int p,int x,int y)
{
    int i,k;
    k=tree[y];
    tree[y]=tree[x];
    graf[p][3]=1;
    ++nr_m_apm;
    apm[nr_m_apm][0]=x;
    apm[nr_m_apm][1]=y;

    tree[k]=tree[y];
    for(i=1; i<=n ;i++)
    {
        if(tree[i]==k)
            tree[i]=tree[k];
    }
    nr++;
}

void kruskal()
{
    int k,n1,n2,a,b,i,p,min;
    for(k=1; k<=m ;k++)
    {
        min=inf;
        for(i=1; i<=m ;i++)
        {
            if(!graf[i][3] && graf[i][2]<min)
            {
                a=graf[i][0];
                b=graf[i][1];
                if(tree[a]!=tree[b])
                {
                    min=graf[i][2];
                    n1=graf[i][0];
                    n2=graf[i][1];
                    p=i;
                }
            }
        }
        if(min==inf) break;
        new_m(p,n1,n2);
        c_total+=min;
    }
}

void print()
{
    int i;
    g<<c_total<<"\n"<<nr<<"\n";
    for(i=1; i<=nr_m_apm ;i++)
    {
        g<<apm[i][0]<<" "<<apm[i][1]<<"\n";
    }
}

int main()
{
    read();
    kruskal();
    print();
    return 0;
}