#include <iostream>
#include <fstream>
#define maxN 200005
#define maxM 400005
#define INF 200000200
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int n,m,cost_t=0,nr=0,saw[maxN],D[maxN],P[maxN];

struct graf
{
    int nod;
    int cost;
    graf *next;
} *G[maxM];

void addN(int x,int y, int z)
{
    graf *q;
    q=new graf;
    q->nod=y;
    q->cost=z;
    q->next=G[x];
    G[x]=q;
}

void read_ini()
{
    f>>n; f>>m;
    int i,a,b,c;
    for(i=1; i<=m ;i++)
    {
        f>>a; f>>b; f>>c;
        addN(a,b,c);
        addN(b,a,c);
    }
    for(i=1; i<=n ;i++)
    {
        saw[i]=0;
        D[i]=INF;
        P[i]=0;
    }
}

void prim_apn(int s)
{
    graf *q;
    int i,k,nod1,nod2,min;
    saw[s]=1;

    for(k=1; k<=n-1 ;k++)
    {
        min=INF;
        nod1=nod2=-1;
        for(i=1; i<=n ;i++)
        {
            q=G[i];
            while(q)
            {
                if(saw[i] && !saw[q->nod])
                {
                    if(q->cost<min)
                    {
                        min=q->cost;
                        nod1=i;
                        nod2=q->nod;
                    }
                }
                q=q->next;
            }
        }
        saw[nod2]=1;
        P[nod2]=nod1;
        D[nod2]=min;
        nr++;
        cost_t+=min;
    }
}

void print()
{
    int i;
    g<<cost_t<<"\n";
    g<<nr<<"\n";
    for(i=2; i<=n ;i++)
    {
        g<<i<<" "<<P[i]<<"\n";
    }
}

int main()
{
    read_ini();
    prim_apn(1);
    print();
    return 0;
}