#include <fstream>
#include <vector>
#include <queue>
#define NMAX 200005

using namespace std;

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

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

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];

vector <gr> L[NMAX];
priority_queue <gr>q;

void alege()
{
    for(auto &v:L[1])
        q.push(v);
    viz[1]=1;
    for(int repet=2; repet<=n; repet++)
    {
        gr minim=q.top();
        while(viz[minim.vfs] == 1)
        {
            q.pop();
            minim=q.top();
        }
        viz[minim.vfs]=1;
        sum+=minim.cost;
        sol[++nr]={0, minim.vfi, minim.vfs};
        for(auto &v:L[minim.vfs])
            q.push(v);
    }
}

int main()
{
    f>>n>>m;

    for(int i=1; i<=m; i++)
    {
        f>>x>>y>>c;
        L[x].push_back({c, x, y});
        L[y].push_back({c, y, x});
    }
    alege();
    g<<sum<<'\n'<<nr<<'\n';
    for(int i=1; i<=nr; i++)
    {
        g<<sol[i].vfi<<' '<<sol[i].vfs<<'\n';
    }
    return 0;
}