#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

vector < pair < int, pair < int, int > > > a;
vector < pair < int, pair < int, int > > >::iterator k;
vector < pair < int, int> > sol;
vector < pair < int, int> >::iterator it;
int x,y,c,rez,i,n,m,t[200004],r[200044];

int root(int x)
{
    if(x!=t[x])
    {
        t[x]=root(t[x]);
    }
    return t[x];
}

void unite(int x,int y)
{
    x=root(x);
    y=root(y);
    if(x==y)
    {
        return;
    }
    if(r[x]<r[y])
    {
        t[x]=y;
    }
    else
    {
        t[y]=x;
    }
    if(r[x]==r[y])
    {
        r[x]++;
    }
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        a.push_back(make_pair(c,make_pair(x,y)));
    }
    sort(a.begin(),a.end());
    for(i=1;i<=n;i++)
    {
        t[i]=i;
        r[i]=0;
    }
    for(k=a.begin();k!=a.end();++k)
    {
        x=(*k).second.first;
        y=(*k).second.second;
        c=(*k).first;
        if(root(x)!=root(y))
        {
            unite(x,y);
            rez+=c;
            sol.push_back(make_pair(x,y));
        }
    }
    printf("%d\n%d\n",rez,sol.size());
    for(it=sol.begin();it!=sol.end();it++)
    {
        printf("%d %d\n",(*it).first,(*it).second);
    }
    return 0;
}