#include <fstream>
#define NMAX 100004
#define MMAX 100004

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

struct Muchie{int x,y,c;} G[MMAX];

int H[MMAX],n,m,h[NMAX],tata[NMAX];
int A[NMAX],cost;//indiciile selectate in APM

void citire();
void creare(int[NMAX],int);
void combinare(int[NMAX],int,int);
int extragere_minim(int[NMAX],int&);
void kruskal();
void afisare();
void Union(int,int);
int Find(int);

int main()
{
    citire();
    kruskal();
    afisare();
    cin.close();cout.close();
    return 0;
}

void kruskal()
{
    int nr=0,mm=m,nmin,cx,cy;
    creare(H,m);
    while (nr<n-1)
    {
        nmin=extragere_minim(H,mm);
        cx=Find(G[nmin].x);
        cy=Find(G[nmin].y);
        if (cx!=cy)
        {
            nr++;
            A[nr]=nmin;
            cost+=G[nmin].c;
            Union(cx,cy);
        }
    }
}

void afisare()
{
    int i;
    cout<<cost<<'\n';
    cout<<n-1<<'\n';
    for (i=1;i<n;i++)
        cout<<G[A[i]].x<<' '<<G[A[i]].y<<'\n';
}

void citire()
{
    int i;
    cin>>n>>m;
    for (i=1;i<=m;i++)
    {
        H[i]=i;
        cin>>G[i].x>>G[i].y>>G[i].c;
    }
}

int Find(int x)
{
    int rad=x,aux;
    //caut radacina
    while (tata[rad]!=0)
        rad=tata[rad];
    while (tata[x])
    {
        aux=tata[x];
        tata[x]=rad;
        x=aux;
    }
    return rad;
}

void Union(int i,int j)
{
    //il fac pe x fiu ai lui y
    //i si j sunt radacinile arborilor care reprezinta radacina x si y
    if (h[i]<h[j])
        tata[i]=j;
    else
    {
        tata[j]=i;
        if (h[i]==h[j])
            h[i]++;
    }
}

void combinare(int H[NMAX],int n,int i)
//se combina nodul H[i] cu heapurile de radacinile 2*i si 2*i+1 obtinand n heap cu radacinile H[i]
{
    int x=H[i],tata,fiu;
    tata=i;fiu=i<<1;
    while (fiu<=n)
    {
        if (fiu+1<=n && G[H[fiu+1]].c<G[H[fiu]].c) fiu++;
        // fiu cel mai mic fiu dintre fii lui x
        if (G[H[fiu]].c<G[x].c)
        {
            H[tata]=H[fiu];
            tata=fiu;
            fiu=tata<<1;
        }
        else break;
    }
    H[tata]=x;
}

void creare(int H[NMAX],int n)
{
    int i;
    for (i=n/2;i>0;i--)
        combinare(H,n,i);
}

int extragere_minim(int H[NMAX],int& n)
{
    int val=H[1];
    H[1]=H[n];
    n--;
    combinare(H,n,1);
    return val;
}