#include <fstream>
#include <algorithm>
#define MMAX 10000
#define NMAX 200

using namespace std;

struct muchie
{
    int x,y; double c;
};

muchie G[MMAX];
int n,m;
int tata[NMAX],h[NMAX];
double costmin;
int sol[NMAX],s,H[NMAX];
int ind,nr,num;

void citire();
void kruskal();
void Union(int i, int j);
int Find(int x);
void Comb_Heap(int rad, int n);
int ExtrageMin(int &n);
void Insert_Heap(int poz, int val);
void Create_Heap(int n);
void afisare();

int main()
{
    citire();
    kruskal();
    afisare();
    return 0;
}

void citire()
{
    ifstream fin("kruskal.in");
    fin>>n>>m;
    nr=m;
    for(int i=1;i<=m;i++)
    {
        fin>>G[i].x>>G[i].y>>G[i].c;
        H[i]=i;
    }
    Create_Heap(nr);
}

void kruskal()
{
    int c1,c2;
    while(s<n-1)
    {
        int i=ExtrageMin(nr);
        c1=Find(G[i].x);
        c2=Find(G[i].y);
        if(c1!=c2)
        {
            costmin+=G[i].c;
            num++;
            sol[++s]=i;
            Union(c1,c2);
        }
    }
}

void Union(int i, int j)
{
    if(h[i]<h[j])
        tata[i]=j;
      else
            if(h[i]>h[j])
                tata[j]=i;
                else
                {
                    tata[i]=j;
                    h[j]++;
                }
}

int Find(int x)
{
    int aux=x,a;
    while(tata[aux])
        aux=tata[aux];
    while(tata[x])
    {
        a=x;
        x=tata[x];
        tata[a]=aux;
    }
    return aux;
}

void afisare()
{
    int i;
    ofstream fout("kruskal.out");
    fout<<costmin<<'\n'<<num<<'\n';
    for(i=1;i<=n-1;i++)
        fout<<G[sol[i]].x<<' '<< G[sol[i]].y<<'\n';
    fout.close();
}

void Comb_Heap(int rad, int n)
{
    int x=G[H[rad]].c,tata=rad,fiu=2*rad;
    int ind=H[rad];
    while (fiu<=n)
    {
        if (fiu+1<=n && G[H[fiu]].c>G[H[fiu+1]].c) fiu++;
        if (x>G[H[fiu]].c)
        {
            H[tata] = H[fiu];
            tata=fiu;
            fiu=2*tata;
        }
        else break;
    }
    H[tata]=ind;
}

int ExtrageMin(int &n)
{
    int x=H[1];
    H[1]=H[n]; n--;
    Comb_Heap(1,n);
    return x;
}

void Create_Heap(int n)
{
    for(int rad=n/2;rad>0;rad--)
        Comb_Heap(rad,n);
}