#include<cstdio>
    #include<algorithm>
    using namespace std;
    #define NMAX 200001
    #define MMAX 400001
    int N , M  , cost , p[NMAX] , grad[NMAX];
    struct muchie
    {
        int x , y , c;
        bool u;
    }m[MMAX];
    bool f(muchie a , muchie b)
    {
        return a.c < b.c;
    }

    void read();
    void solve();
    void write();
    int point( int x);
    void link(int x , int y);

    int main()
    {
        read();
        solve();
        write();
        return 0;
    }

    void read()
    {
        freopen("apm.in" , "r" , stdin );
        scanf("%d%d" , &N  ,&M );
        for(int i = 1 ; i<= M ; ++i )
            scanf("%d%d%d" , &m[i].x , &m[i].y , &m[i].c);
    }

    void solve()
    {
        sort(m+1,m+M+1,f);
        int i = 1 , k = 0;
        for(int i = 1 ; i<= N ; ++i )
            p[i] = i;
        while(i < N)
        {
            k++;
            if(point(m[k].x) != point(m[k].y))
            {
                link(point(m[k].x),point(m[k].y));
                i++;
                m[k].u = 1;
                cost += m[k].c;
            }
        }
    }

    int point(int x)
    {
        int aux = x , aux1;
        while(aux != p[aux])
            aux=p[aux];
        while(x != p[x])
        {
            aux1 = p[x];
            p[x] = aux;
            x = aux1;
        }
        return x;
    }

    void link(int x , int y)
    {
        if(grad[x] >= grad[y])
        {
            p[y] = x;
            grad[x]++;
        }
        else
        {
            p[x] = y;
            grad[y]++;
        }
    }

    void write()
    {
        freopen("apm.out" , "w" , stdout );
        printf("%d\n%d\n" , cost , N-1);
        for(int i = 1 ; i<= M ; ++i )
            if(m[i].u)
            printf("%d %d\n" , m[i].x , m[i].y );
    }