#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

typedef vector<int> VI;

struct tip_muchie
    {
    int x,y,c;
    }*mc;
vector<tip_muchie> muc;
VI m_sort,P,apm,ad;
int n,m,i,px,py,ctot;

int det_P(int &x)
    {
    if(x!=P[x]) return det_P(P[x]);
    return P[x];
    }

inline bool cmp(int a,int b)
    {
    return muc[a].c<muc[b].c;
    }
int main()
    {
    f>>n>>m;
    P.resize(n+1);
    for(i=1; i<=n; ++i) P[i]=i;
    muc.resize(m+1);
    m_sort.resize(m+1);
    ad.resize(n+1,0);

    for(i=1; i<=m; ++i)
        {
        f>>muc[i].x>>muc[i].y>>muc[i].c;
        m_sort[i]=i;
        }

    sort(m_sort.begin()+1,m_sort.begin()+m+1,cmp);
    for(i=1; i<=m; ++i)
        {
        mc = &muc[m_sort[i]];
        px=det_P(mc->x);
        py=det_P(mc->y);
        if(px!=py)
            {
            apm.push_back(m_sort[i]);
            ctot+=mc->c;
            if(ad[px]<ad[py]) P[px]=py;
            else P[py]=px;
            if(ad[px]==ad[py]) ++ad[px];
            }
        }
    g<<ctot<<'\n';
    g<<apm.size()<<'\n';
    for(i=0;i<apm.size();++i) g<<muc[apm[i]].x<<' '<<muc[apm[i]].y<<'\n';
    return 0;
    }