#include <bits/stdc++.h>
#define lim 200005
using namespace std;

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

int n, m, arb[lim], cost=0;
struct muchii
{
    int c, xx, yy;
};
vector <pair <int, int> > v[lim];
vector <muchii> muc;
vector <muchii> r;
bool cond(muchii x, muchii y)
{
    return x.c<y.c;
}

void read()
{
    in>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        int x, y, z;
        in>>x>>y>>z;
        v[y].push_back(make_pair(x, z));
        v[x].push_back(make_pair(y, z));
        muchii a;
        a.c=z;
        a.xx=x;
        a.yy=y;
        muc.push_back(a);
    }
    sort(muc.begin(),muc.begin()+m, cond);
    for(int i=1; i<=n; ++i)
    {
        arb[i]=i;
    }
    /*for(int i=0; i<m; ++i)
    {
        cout<<muc[i].xx<<" "<<muc[i].yy<<" "<<muc[i].c<<'\n';
    }*/
}

void Kruskal()
{
    for(int i=0; i<m; ++i)
    {
        if(arb[muc[i].xx]!=arb[muc[i].yy])
        {
            r.push_back(muc[i]);
            cost+=muc[i].c;
            int a=arb[muc[i].yy];
            for(int j=1; j<=n; ++j)
            {
                if(arb[j]==a)
                {
                    arb[j]=arb[muc[i].xx];
                }
                //cout<<arb[j]<<" ";
            }
            //cout<<'\n';
        }
    }
}

void afis()
{
    out<<cost<<'\n';
    out<<r.size()<<'\n';
    for(int i=0; i<r.size(); ++i)
    {
        out<<r[i].xx<<" "<<r[i].yy<<'\n';
    }
}

int main()
{
    read();
    Kruskal();
    afis();
    return 0;
}