#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];
int c[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;
}*/

int Find()
{

}
void Union(int x,int y)
{
    if(c[x]>c[y])
    {
        c[x]+=c[y];
        t[y] = x;
    }
    else
    {
        c[y]+=c[x];
        t[x] = y;
    }
}
int Find(int i)
{
    if(t[i]!=i)
    t[i] = Find(t[i]);
    return t[i];
}
void Solve()
{
    sort(a+1,a+m+1,Cmp);
    int v1,v2,i;
    for(i=1;i<=n;i++)
    {
        t[i] = i;
        c[i] = 1;
    }
    int k = n-1;

    for(i=1;i<=m && k>0;i++)
    {
       v1 = Find(a[i].x);
       v2 = Find(a[i].y);
       if(v1 != v2)
       {
           Union(v1,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;
}