#include <bits/stdc++.h>

using namespace std;

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

int n,m,cost,p[200003],r[200003];
struct muchie{int x; int y; int c; friend bool operator <(muchie m1, muchie m2){return(m1.c<m2.c ||(m1.c==m2.c && m1.x<m2.x) || (m1.c==m2.c && m1.x==m2.x && m1.y<m2.y));}};
set<muchie>v;
vector<pair<int, int> >APM;

int Find(int x)
{
    if(x!=p[x]) p[x]=Find(p[x]);
    return p[x];
}

void Union(int x, int y)
{
    int xroot,yroot;
    xroot=Find(x); yroot=Find(y);
    if(r[xroot]<r[yroot])
    {
        r[yroot]+=r[xroot];
        p[xroot]=yroot;
    }
    else
    {
        r[xroot]+=r[yroot];
        p[yroot]=xroot;
    }
}

void make_set()
{
    int i;
    for(i=1;i<=n;i++) {
        p[i]=i;
        r[i]=1;
    }
}

int main()
{
    //g<<1;
    int a,b,c,i;
    muchie aux;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        aux.x=a; aux.y=b; aux.c=c;
        v.insert(aux);
    }
    make_set();
    set<muchie>::iterator it;
    for(it=v.begin();it!=v.end();++it)
    {
        a=it->x; b=it->y; c=it->c;
        if(Find(a)!=Find(b))
        {
            Union(a,b);
            cost+=c;
            APM.push_back(make_pair(a,b));
        }
    }
    g<<cost<<'\n'<<APM.size()<<'\n';
    vector<pair<int, int> >::iterator it1;
    for(it1=APM.begin();it1!=APM.end();it1++)
        g<<it1->first<<' '<<it1->second<<'\n';
    f.close();
    g.close();
    return 0;
}