#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define NMax 200001

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

struct muchie{int x,y,t;};

class Compare {
public:
    bool operator()(muchie& t1,muchie& t2)
    {
        if(t1.t>t2.t) return true;
        return false;
    }
};

priority_queue<muchie, vector<muchie>, Compare> cd;
vector<int> v[NMax],w[NMax],solx,soly;
int n,m,viz[NMax],nrnod,nrm,sum;

void add(int s)
{
    muchie u;
    int i,e;
    e=v[s].size();
    for(i=0;i<e;i++) if(viz[v[s].at(i)]==0)
    {
        u.x=s;
        u.y=v[s].at(i);
        u.t=w[s].at(i);
        cd.push(u);
    }
}

void prim(int s)
{
    muchie u;
    viz[s]=1;
    add(s);
    nrnod=1;

    while(nrnod<n)
    {
        u=cd.top();
        cd.pop();
        if(!viz[u.y])
        {
            nrm++;
            sum+=u.t;

            solx.push_back(u.x);
            soly.push_back(u.y);

            viz[u.y]=1;
            nrnod++;
            add(u.y);
        }
    }
}

int main()
{
    int i,a,b,c;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        v[a].push_back(b);
        w[a].push_back(c);
        v[b].push_back(a);
        w[b].push_back(c);
    }

    prim(1);

    g<<sum<<"\n"<<nrm<<"\n";
    for(i=0;i<nrm;i++) g<<solx.at(i)<<" "<<soly.at(i)<<"\n";

    f.close();
    g.close();
    return 0;
}