#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

typedef vector<pair<int,int> > VPI;
#define mp make_pair
#define foor(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();++it)

vector<VPI> G;
VPI apm;
vector<bool> in_apm;
struct eee{int c,to,from;
bool operator<(eee d) const
{
    return c>d.c;
}
};
priority_queue<eee> heap;

int n,m,x,y,c,nod,ctot;

inline eee me(int c,int to,int from)
{
    eee n;
    n.c=c;n.to=to;n.from=from;
    return n;
}
int main()
{
    f>>n>>m;
    G.resize(n+1);
    in_apm.resize(n+1);
    for(;m;--m)
    {
        f>>x>>y>>c;
        G[x].push_back(mp(y,c));
        G[y].push_back(mp(x,c));
    }

    in_apm[1]=true;
    foor(it,G[1]) heap.push(me(it->second,it->first,1));

    while(!heap.empty())
    {
        nod=heap.top().to;
        apm.push_back(mp(heap.top().to,heap.top().from));
        ctot+=heap.top().c;
        in_apm[nod]=true;
        foor(it,G[nod]) if(!in_apm[it->first])
                heap.push(me(it->second,it->first,nod));

        while(!heap.empty() && in_apm[heap.top().to]) heap.pop();
    }
    g<<ctot<<'\n';
    g<<apm.size()<<'\n';
    foor(it,apm) g<<it->first<<' '<<it->second<<'\n';
    return 0;
}