#include <bits/stdc++.h>
using namespace std;
ifstream f ( "test.in" );
ofstream g ( "test.out" );
int tati[200005],rang[200005],rasp;
vector < pair < int , int > > muchii;
struct costuri
{   int cost,a,b;

}v[400005];
bool compar(costuri a , costuri b)
{
    return a.cost<b.cost;
}
int reprezentant(int nod)
{   if(tati[nod]==nod) return nod;
    return (tati[nod]=reprezentant(tati[nod]));
}
int main()
{   int n,m;
    f>>n>>m;
    for(int i=1;i<=n;i++)
    {   tati[i]=i;
        rang[i]=1;
    }
    for(int i=1;i<=m;i++) f>>v[i].a>>v[i].b>>v[i].cost;
    sort(v+1,v+m+1,compar);
    for(int i=1;i<=m;i++)
    {   int ra=reprezentant(v[i].a);
        int rb=reprezentant(v[i].b);
        if(ra!=rb)
        {   if(rang[ra]>rang[rb])
            {   rang[ra]+=rang[rb];
                tati[rb]=ra;
            }
            else
            {   rang[rb]+=rang[ra];
                tati[ra]=rb;
            }
            muchii.push_back({v[i].b,v[i].a});
            rasp+=v[i].cost;
        }
    }
    g<<rasp<<'\n';
    g<<muchii.size()<<'\n';
    for(int i=0;i<muchii.size();i++)
        g << muchii[i].first<< ' '<<muchii[i].second << '\n';
    return 0;
}