#include <fstream>
#include <queue>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct much{
    int in,c;
    bool friend operator>(much a,much b)
    {
        return a.c>b.c;
    }
};
struct muchie{
    int x,y;
}mc[400005];
int comp(much a,much b)
{
    return a.c<b.c;
}
priority_queue <much,vector<much>,greater<much> > q;
int t[200005],viz[200005];
int root(int x)
{
    if(t[x]==0)
        return x;
    t[x]=root(t[x]);
    return t[x];
}
int main()
{
    int n,m,i,sel,rez;
    much c;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>mc[i].x>>mc[i].y>>c.c;
        c.in=i;
        q.push(c);
    }
    sel=0;rez=0;
    for(i=1;sel<n-1;i++)
    {
        c=q.top();
        q.pop();
        int k,a;
        k=root(mc[c.in].x);
        a=root(mc[c.in].y);
        if(k!=a)
        {
            sel++;
            viz[c.in]=1;
            rez+=c.c;
            t[a]=root(k);
        }
    }
    fout<<rez<<'\n'<<n-1<<'\n';
    for(i=1;i<=m;i++)
        if(viz[i]==1)
            fout<<mc[i].x<<' '<<mc[i].y<<'\n';
    return 0;
}