#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

int n,m,x,y,c,nr;
struct muchii
{
    int a,b,cost;
}aux;

struct cmp
{
  bool operator()(const muchii& a, const muchii& b) const
  {
    return (a.cost > b.cost);
  }
};


priority_queue <muchii, vector<muchii>, cmp> Q;
vector<int> T,R;
vector<muchii> M;

int find(int x)
{
    int y=x;

    while (T[x]!=x)
    {
        x=T[x];
    }

    T[y]=x;
    return x;
}

void join(int x, int y)
{
    x=find(x); // find(x) = componenta conexa din care face parte x
    y=find(y);
    if (R[x]>R[y])
         T[y]=x;
    if (R[x]<R[y])
         T[x]=y;
    if (R[x]==R[y])
    {
        T[x]=y;
        R[y]++;
    }
}

void kruskal()
{
    c=0;
    nr=0;
    while (!Q.empty())
    {
        aux=Q.top();
            Q.pop();

        if(find(aux.a)!=find(aux.b))
        {
            join(aux.a, aux.b);
            c+=aux.cost;
            nr++;
            M.push_back(aux);
        }

    }
}

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

    f>>n>>m;

    for(int i=0; i<=n; i++)
    {
        T.push_back(i);
        R.push_back(0);
    }

    for(int i=0; i<m; i++)
    {
        f>>x>>y>>c;
        aux.a=x;
        aux.b=y;
        aux.cost=c;
        Q.push(aux);
    }

    kruskal();

    g<<c <<"\n" << nr << "\n";

    for(int i=0; i<M.size(); i++)
    {
        g<<M[i].a << " " << M[i].b << "\n";
    }

    f.close();
    g.close();
    return 0;
}