#include <fstream>
#include <queue>
#define NMAX 200005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,tata[NMAX],h[NMAX],S,nr,c1,c2;
struct Muchie
{
    int x,y,c;
    friend bool operator > (Muchie, Muchie);
}a,s[NMAX];
bool operator > (Muchie a, Muchie b)
{
    return a.c>b.c;
}
priority_queue <Muchie, vector <Muchie> , greater <Muchie> > H;
int Find(int x)
{
    int k=x;
    while(tata[k])
        k=tata[k];
    ///comprim drumul
    while(tata[x])
    {
        int aux=tata[x];
        tata[x]=k;
        x=aux;
    }
    return k;
}
void Union(int x, int y)
{
    int X=Find(x), Y=Find(y);
    if(h[X]>h[Y]) tata[Y]=X;
    else if(h[X]<h[Y]) tata[X]=Y;
    else {tata[Y]=X; h[X]++;}
}
int main()
{
    int i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a.x>>a.y>>a.c;
        H.push(a);
    }
    while(nr<n-1)
    {
        a=H.top(); H.pop();
        c1=Find(a.x);
        c2=Find(a.y);
        if(c1!=c2)
        {
            S+=a.c;
            s[++nr]=a;
            Union(c1,c2);
        }
    }
    fout<<S<<'\n'<<n-1<<'\n';
    for(i=1;i<n;i++)
        fout<<s[i].x<<' '<<s[i].y<<'\n';
    return 0;
}