#include<fstream>
#include<vector>
#include<queue>
#include<utility>
#define pi pair<int, int>
using namespace std;
struct edge
{
    int nod1, nod2, cost;
};
struct cmp
{
    bool operator() ( const edge &edge1, const edge &edge2) const
    {
        return edge1.cost>edge2.cost;
    }
};

int apm_cost;
queue<pi>sol;
vector< vector<pi> >m(400001);
bool ch[200001];
ofstream g("apm.out");

void prim(int root, int n);
int main()
{
    ifstream f("apm.in");
    int n, nrm, i, x, y, c;
    f>>n>>nrm;
    for(i=1;i<=nrm;i++)
    {
        f>>x>>y>>c;
        m[x].push_back(make_pair(y, c));
        m[y].push_back(make_pair(x, c));
    }
    /*for(i=1;i<=n;i++)
    {
        if(!m[i].empty())
        {
            g<<i;
            for(vector<pi>::iterator it=m[i].begin();it!=m[i].end();++it, g<<"\n")
                g<<":  ("<<(*it).first<<" "<<(*it).second<<") ";
        }
    }*/
    prim(1, n);
    g<<apm_cost<<"\n";
    g<<sol.size()<<"\n";
    while(!sol.empty())
        g<<sol.front().first<<" "<<sol.front().second<<"\n", sol.pop();
    f.close();
    g.close();
    return 0;
}
void prim(int root, int n)
{
    ch[root]=true;
    edge e, e2;
    priority_queue<edge, vector<edge>, cmp> Q;
    for(vector<pi>::iterator it=m[root].begin(); it!=m[root].end();++it)
        if(!ch[(*it).first])
        {
            e.nod1=root;
            e.nod2=(*it).first;
            e.cost=(*it).second;
            Q.push(e);
        }
    for(int i=1;i<n;i++)
    {
        e=Q.top();
        Q.pop();
        while(ch[e.nod1] && ch[e.nod2])
        {
            e=Q.top();
            Q.pop();
        }
        apm_cost+=e.cost;
        ch[e.nod2]=ch[e.nod1]=true;
        e2.nod1=e.nod2;
        for(vector<pi>::iterator it=m[e.nod2].begin(); it!=m[e.nod2].end(); ++it)
            if(!ch[(*it).first])
            {
                e2.nod2=(*it).first;
                e2.cost=(*it).second;
                Q.push(e2);
            }
        sol.push(make_pair(e.nod1, e.nod2) );
    }
}