#include <bits/stdc++.h>
using namespace std;
struct cows
{
    int x,y,val;
};
cows v[400005];
cows rez[400005];
int prt[200005];
int add[200005];
bool Cmp(cows a,cows b)
{
    return a.val<b.val;
}
int Fnd(int a)
{
    if(prt[a]==a)
        return a;
    return prt[a]=Fnd(prt[a]);
}
bool Comp(int a,int b)
{
    a=Fnd(a);
    b=Fnd(b);
    if(a==b)
        return true;
    if(add[b]>add[a])
        swap(a,b);
    prt[b]=a;
    add[a]+=add[b];
    add[b]=0;
    return false;

}
int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        prt[i]=i;
        add[i]=1;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>v[i].x>>v[i].y>>v[i].val;
    }
    sort(v+1,v+m+1,Cmp);
    int rezvl=0,k=0;
    for(int i=1;i<=m;i++)
    {
        int a=v[i].x;
        int b=v[i].y;
        if(Comp(a,b)==false)
        {
            rezvl+=v[i].val;
            rez[k].x=a;
            rez[k].y=b;
            k++;

        }
    }
    cout<<rezvl<<'\n';
    cout<<k<<'\n';
    for(int i=0;i<k;i++)
    {
        cout<<rez[i].x<<" "<<rez[i].y<<'\n';
    }
    return 0;
}