#include <bits/stdc++.h>
#define NMAX 200010
using namespace std;
ifstream f ("apm.in") ;
ofstream g ("apm.out") ;
int N , M , cost = 0 , muchii=0;
int T[NMAX] , h[NMAX] ;
struct didi
{
    int x;
    int y;
    int c;
}mch[2*NMAX],sol[NMAX];
bool cmp (didi a , didi b)
{
    return(a.c<b.c) ;
}
int TATA (int x)
{
    while (x != T[x]) return TATA(T[x]);
    return x;
}
int muchie (int a ,int b)
{
    int r1,r2;
    r1 = TATA(a);
    r2 = TATA(b) ;
    if (r1 == r2) return 0 ;
    else if (h[r1]<h[r2]) T[r1]=r2;
    else if (h[r1]>h[r2]) T[r2]=r1;
    else
    {
        T[r2]=r1;
        h[r2] ++ ;
    }

}
void KRUSKAL()
{
    int r1,r2,k=1;
     muchii = 0;
     muchii = 0;
    while (muchii < N-1)
    {
        int a = mch[k].x;
        int b = mch[k].y;
        if (muchie(a,b))
        {
            cost += mch[k].c;
            muchii ++ ;
            sol[muchii].x =a;
            sol[muchii].y =b;
        }
        k ++ ;
    }
}
int main()
{
    f >> N >> M ;
    for (int i = 1 ;  i <= M ; ++i)
    {
        f >> mch[i].x >> mch[i].y >> mch[i].c;
    }
    sort(mch+1,mch+M+1,cmp);
    for  (int i = 1 ; i <= N ; ++i) {T[i] = i ; h[i] = 1;}
    KRUSKAL();
    g << cost << '\n';
    g << muchii << '\n';
    for (int i = 1 ; i <= muchii ; ++i)
        g << sol[i].x << ' ' << sol[i].y << '\n';
}