#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define DIM 200020
using namespace std;
int t[DIM],r[DIM];
int n,m1;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
struct muchie
{
    int x,y,c;
};
vector <muchie> m,apm;
bool compare (muchie a,muchie b)
{
    return (a.c<b.c);
}
int Find (int x)
{
    int rad,elem;
    rad=x;
    while (t[rad]!=0)
        rad=t[rad];
    while (t[x]!=0)
    {
        elem=t[x];
        t[x]=rad;
        x=elem;
    }
    return rad;
}
void Union (int x,int y)
{
    if (r[x]<r[y])
        t[x]=y;
    else if (r[x]>r[y])
            t[y]=x;
         else
         {
             t[x]=y;
             r[y]++;
         }
}
int main()
{
    long long costapm=0;
    muchie h;
    int rad1,rad2,i;
    fin>>n>>m1;
    for (i=0;i<m1;i++)
    {
        fin>>h.x>>h.y>>h.c;
        m.push_back(h);
    }
    sort(m.begin(),m.end(),compare);
    int nr=1,j=0;
    while (nr<n&&j<m1)
    {
        rad1=Find(m[j].x);
        rad2=Find(m[j].y);
        if (rad1!=rad2)
        {
            costapm=costapm+m[j].c;
            apm.push_back(m[j]);
            Union(rad1,rad2);
            nr++;
        }
        j++;
    }
    fout<<costapm<<"\n"<<n-1<<"\n";
    for (i=0;i<apm.size();i++)
        fout<<apm[i].x<<" "<<apm[i].y<<"\n";
    fin.close();
    fout.close();
    return 0;
}