#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int tata[200005],rang[200005],sum,n,m,i;
vector <pair <int,int> > sol;
struct wow
{
    int x,y,cost;
}v[400005];
int repr (int x)
{
    if (tata[x]!=x)
    {
        return repr(tata[x]);
    }
    return tata[x];
}
void uneste (int x,int y)
{
    x=repr(x);
    y=repr(y);
    if (rang[x]<rang[y])
    {
        tata[x]=y;
    }
    else
    if (rang[x]>rang[y])
    {
        tata[y]=x;
    }
    else
    {
        rang[x]++;
        tata[y]=x;
    }
}
bool compare (wow a,wow b)
{
    return a.cost<b.cost;
}
int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
    {
        f>>v[i].x>>v[i].y>>v[i].cost;
    }
    for (i=1;i<=n;i++)
    {
        rang[i]=1;
        tata[i]=i;
    }
    sort (v+1,v+m+1,compare);
    for (i=1;i<=m;i++)
    {
        if (repr(v[i].x)!=repr(v[i].y))
        {
            uneste(v[i].x,v[i].y);
            sol.push_back({v[i].x,v[i].y});
            sum+=v[i].cost;
        }
    }
    g<<sum<<'\n'<<sol.size()<<'\n';
    for (i=0;i<sol.size();i++)
    {
        g<<sol[i].first<<" "<<sol[i].second<<'\n';
    }
    return 0;
}