#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;
struct nod {
    int x,y,cost;
    inline nod ( int _x, int _y, int _cost) {
        x=_x;
        y=_y;
        cost=_cost;
    }
    inline bool operator < (const nod &c) const {
        return cost>c.cost;
    }
};
vector <nod> v[200001],a;
priority_queue <nod> c;
bitset <200001> d;
int main ()
{
    int n,m,x,y,cost,i,sum;
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    for(i=1;i<=m;i++) {
        f>>x>>y>>cost;
        v[x].push_back(nod(x,y,cost));
        v[y].push_back(nod(y,x,cost));
    }
    f.close();
    for(vector <nod> :: iterator it=v[1].begin();it!=v[1].end();it++) 
        c.push(nod(it->x,it->y,it->cost));
    d[1]=1;
    sum=0;
    for(i=2;i<=n;i++) {
        while(d[c.top().x]!=1 || d[c.top().y]!=0 )
            c.pop();
        a.push_back(nod(c.top().x,c.top().y,0));
        sum=sum+c.top().cost;
        y=c.top().y;
        d[y]=1;
        c.pop();
        for(vector <nod> :: iterator it=v[y].begin();it!=v[y].end();it++)
            if(d[it->y]==0)
                c.push(nod(y,it->y,it->cost));
    }
    g<<sum<<'\n'<<a.size()<<'\n';
    for(vector <nod> :: iterator it=a.begin();it!=a.end();it++)
        g<<it->x<<" "<<it->y<<'\n';
    g.close();
    return 0;
}