#include <bits/stdc++.h>

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