#include <fstream>
#include <algorithm>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
int m,n;
int cost;
int k1;
struct muchie
{
    int x,y,c;
};
muchie a[400002];
int t[200002];
struct sub{int x,y;}b[200002];
inline bool Cmp(muchie a, muchie b)
{
    return a.c < b.c;
}
void Citire()
{
    int i;
    int x1,y1,c1;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x1>>y1>>c1;
        a[i].x = x1;
        a[i].y = y1;
        a[i].c = c1;
    }
}
void Union(int x,int y)
{
    int i;
    for(i=1;i<=n;i++)
    if(t[i] == y)
    t[i] = x;


}
void Solve()
{
    sort(a+1,a+m+1,Cmp);
    int v1,v2,i;
    for(i=1;i<=n;i++)
    t[i] = i;
    int k = n-1;

    for(i=1;i<=m && k>0;i++)
    {
       v1 = a[i].x;
       v2 = a[i].y;
       if(t[v2] != t[v1])
       {
           Union(t[v1],t[v2]);
           k--;
           cost += a[i].c;
           k1++;
           b[k1].x=v1;
           b[k1].y=v2;
       }
    }

}
int main()
{
    Citire();
    Solve();
    g<<cost<<"\n";
    g<<k1<<"\n";
    for(int i=1;i<=k1;i++)
    g<<b[i].x<<" "<<b[i].y<<"\n";
    return 0;
}