#include <fstream>
#define MAX 200000
using namespace std;


int n, m;
struct muchie{
    int v1, v2;
    int val;
};

muchie a[MAX];
muchie arb[MAX];
int p[MAX];
int h[MAX];
int cost;


ifstream fin("apm.in");
ofstream fout("apm.out");
void Read();
void Sort(int ,int);
void Init();
int Cauta(int);
void Unire(int, int);
void Afis();
void Kruskal();





int main()
{
    Read();
    Kruskal();
    Afis();
    
    
    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    fin >> n;
    fin >> m;
    for (int i = 1; i<=m; i++)
    {
        fin >> a[i].v1;
        fin >> a[i].v2;
        fin >> a[i].val;
    }
}

void sort(int x,int y)  
{    int i,j,p;  
     muchie aux;  
     if(x<y)  
      {  i=x-1;  
     j=y+1;  
     p=a[(x+y)/2].val;  
     while(i<j)  
     {   do i++; while(a[i].val<p);  
         do j--; while(a[j].val>p);  
         if(i<j) {  aux=a[i];  
                a[i]=a[j];  
                a[j]=aux;  
             }  
     }  
     sort(x,i-1);  
     sort(j+1,y);  
      }  
}  

void Init()
{
    for (int i = 1; i<=n; i++)
    {
        p[i] = i;
        h[i] = 0;
    }
}

void Unire(int x, int y)
{
    if (h[x] > h[y])
    {
        p[y] = x;
    }
    else
    {
        p[x] = y;
        if (h[x] == h[y]) ++h[y];
    }
}

int Cauta(int x)
{
    if (x != p[x]) p[x] = Cauta(p[x]);
    return p[x];
}

void Kruskal()
{
    sort(1,m);
    int k = 0;
    Init();
    
    for (int i = 1; i <= m; i++)
    {
        int r1 = Cauta(a[i].v1);
        int r2 = Cauta(a[i].v2);
        //fout << a[i].v1 << " " << a[i].v2 << "\n";
        if (r1 != r2)
        {
            cost += a[i].val;
            arb[++k] = a[i];
            Unire(r1, r2);
            if (k == n-1) break;
        }
    }
}

void Afis()
{
    fout << cost << "\n";
    fout << n-1 << "\n";
    for (int i = 1; i <= n-1; i++)
    {
        fout << arb[i].v1 << " " << arb[i].v2 << "\n";
    }
}