#include <fstream>
#include <algorithm>
#define NMAX 200005
#define MMAX 400005

using namespace std;

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

int n, m, x, y, c, sum, nr, tati[NMAX];

struct gr{
    int cost, vfi, vfs;
//    bool operator<(const gr &a) const{
//        if(a.cost == this->cost)
//            return a.vfs<this->vfs;
//        return a.cost<this->cost;
//    }
}sol[NMAX], muc[MMAX];

bool cmp(gr A, gr B){
    if(A.cost == B.cost)
        return A.vfs<B.vfs;
    return A.cost<B.cost;
}

int root(int x)
{
    if(tati[x] == x)
        return x;
    int aux=root(tati[x]);
    tati[x]=aux;
    return aux;
}
int ok;
void intrebare(int x, int y)
{
    int v1=root(x);
    int v2=root(y);
    if(v1 != v2)
    {
        tati[v2]=v1;
        ok=1;
    }
}

void connect()
{
    for(int i=1; i<=m && nr<=n-1; i++)
    {
        ok=0;
        intrebare(muc[i].vfi, muc[i].vfs);
        if(ok == 1)
        {
            sum+=muc[i].cost;
            sol[++nr]={0, muc[i].vfi, muc[i].vfs};
        }
    }
}

int main()
{
    f>>n>>m;
    for(int i=1; i<=n; i++)
        tati[i]=i;
    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>c;
        muc[i]={c, x, y};
    }
    sort(muc+1, muc+1+m, cmp);
    connect();
    g<<sum<<'\n'<<nr<<'\n';
    for(int i=1; i<=nr; i++)
    {
        g<<sol[i].vfi<<' '<<sol[i].vfs<<'\n';
    }
    return 0;
}