#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

#define pb push_back
#define f first
#define sf second.first
#define ss second.second
#define mp make_pair
#define p pair<int,pair<int,int> >
#define p2 pair<int,int>
#define pq priority_queue
#define DIM 200005

struct cmp {
    
    bool operator()(const p &x,const p &y)
    {
        return (x.ss<y.ss || (x.ss==y.ss && x.f<y.f || (x.f==y.f && x.sf<y.sf)));
    }
};

vector <p> a;
vector <p2> s;

int n,m,r[DIM],t[DIM],sol;
int find (int &x)
{
    if(x != t [x])
    x= find( t[ x ] ); 
    return t[x] ;
}
void unite (int x,int y)
{
    if(r[x]>r[y])
    {
        unite(y,x);
        return ;
    }
    r[y]+=r[x];
    t[x]=y;
}

void read ()
{
    int i,x,y,c;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        a.pb (mp(x,mp(y,c)));
    }
}
void solve ()
{
    int i,n1,n2;
    for(i=1;i<=n;++i)
        t[i]=i;
    for(i=0;i<a.size ();++i)
    {
        n1=find(a[i].f);
        n2=find(a[i].sf);
        if(n1!=n2)
        {            
            sol+=a[i].ss;
            s.pb (mp(n1,n2));
            unite(n1,n2);
        }
    }
}
void show ()
{
    int i;
    printf("%d\n%d\n",sol,s.size ());
    for(i=0;i<s.size ();++i)
        printf("%d %d\n",s[i].f,s[i].second);
}
int main ()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    read ();
    sort(a.begin (),a.end (),cmp ());
    solve ();
    show ();
    return 0;
}