#include <fstream>
#include <queue>
#include <functional>
#include <vector>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int tata[1001],h[1001];
struct muchie{
    int c,x,y;
    friend bool operator>(muchie a,muchie b);
};
bool operator>(muchie a,muchie b)
{
    return a.c>b.c;
}
muchie v[1000];
int n,m;

class cmp
{
public:
    bool operator()(muchie a,muchie b)
    {
        return a.c<b.c;
    }
};


priority_queue <muchie,vector<muchie>, greater<muchie> > heap;
void citire()
{
    muchie aux;
    fin>>n>>m;
    for(int i=0;i<m;i++){
        fin>>aux.x>>aux.y>>aux.c;
        heap.push(aux);
    }
}
void afisare()
{
    int sum=0;
    for(int i=0;i<n-1;i++)
        sum+=v[i].c;
    fout<<sum<<'\n'<<n-1<<'\n';
    for(int i=0;i<n-1;i++)
    {
        fout<<v[i].x<<' '<<v[i].y<<'\n';
    }
}
void Union(int x,int y) // reunesc arborele cu radacina x cu arborele cu radacina y cu regula ponderala
{
    if(h[x]<h[y])
    {
        tata[x]=y;
        return ;
    }
    if(h[x]>h[y])
    {
        tata[y]=x;
        return ;
    }
    tata[y]=x;
    h[y]++;
}
int Find(int x) // returneaza radacina arborelui din care face parte x aplic si compresia drumului;
{
    int rad,aux;
    rad=x;
    while(tata[rad])
        rad=tata[rad];
    while (x!=rad)
    {
        aux=tata[x];
        tata[x]=rad;
        x=aux;
    }
    return rad;
}
int main()
{
    int cx,cy;
    muchie aux;
    citire();
    for(int nrsel=0;nrsel<n-1;)
    {
        aux=heap.top();
        heap.pop();
        cx=Find(aux.x);
        cy=Find(aux.y);
        if(cx!=cy)
        {
            v[nrsel++]=aux;
            Union(cx,cy);
        }
    }
    afisare();
    return 0;
}