#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#define maxn 100001

using namespace std;

    ifstream f("apm.in");
    ofstream g("apm.out");

    struct muc{
        int x;
        int y;
        int c;
    };

    int n,m;
    muc muchii[maxn];

    void citire()
    {
        f>>n>>m;
        for(int i = 1;i<=m;i++)
        {
            int x,y,c;
            f>>x>>y>>c;
           muchii[i].x = x;
           muchii[i].y = y;
           muchii[i].c = c;
        }
        f.close();
    }

    int cmp(muc a,muc b)
    {
        return(a.c < b.c);
    }

    int comp[maxn],nr_sol,sum_sol;
    muc sol[maxn];

    void init()
    {
        for(int i = 1; i<=n;i++)
        {
            comp[i] = i;
        }
    }

    void KRUSKAL()
    {
        init();

//        int nr_folos = 0;
        int i = 1;
        while(nr_sol < n-1)
        {
            int x,y,a;

            x = muchii[i].x;
            y = muchii[i].y;
            a = comp[y];
            if(comp[x]!=comp[y])
            {
                for(int  j = 1;j<=n; ++j)
                {
                    if(comp[j] == a) comp[j] = comp[x];
                }
//                nr_folos++;
                nr_sol++;
                sol[nr_sol] = muchii[i];
                sum_sol += muchii[i].c;
            }
            i++;
//            cout<<nr_folos;

        }
    }

    void afis()
    {
        g<<sum_sol<<endl;
        g<<nr_sol<<endl;
        for(int i = 1;i<=nr_sol;i++)
        {
            g<<sol[i].x<<" "<<sol[i].y<<endl;
        }
    }




int main()
{
    citire();
    sort(muchii+1, muchii+m+1,cmp);
    KRUSKAL();
    afis();


    return 0;
}