#include <cstdio>
#include <queue>
#define Nmax 200010
using namespace std;

struct legatura
{
    int nod1,nod2,cost;
    bool operator < (const legatura &t) const
    {
        return t.cost<cost;
    }
};

int n,m,leg[Nmax],rot[Nmax];
long long rez;
priority_queue <legatura> c;
queue < pair<int,int> > muchii;

int root(int x)
{
    int beg=x,var=x,f;
    while(rot[beg]!=beg) beg=rot[beg];
    while(rot[var]!=var)
    {
        f=var;
        var=rot[var];
        rot[f]=beg;
    }
    return beg;
}

void unite(int x,int y)
{
    rot[y]=rot[x];
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int i,n1,n2,price;
    legatura l;

    scanf("%d%d",&n,&m);
    for(;m;m--) { scanf("%d%d%d",&n1,&n2,&price); l.nod1=n1; l.nod2=n2; l.cost=price; c.push(l); }
    for(i=1;i<=n;i++) rot[i]=i;

    while(!c.empty())
    {
        l=c.top(); c.pop();
        if(root(l.nod1)!=root(l.nod2))
        {
            rez+=l.cost;
            muchii.push(make_pair(l.nod1,l.nod2));
            unite(root(l.nod1),root(l.nod2));
        }
    }

    printf("%lld\n%d\n",rez,muchii.size());
    while(!muchii.empty())
    {
        printf("%d %d\n",muchii.front().first,muchii.front().second);
        muchii.pop();
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}