#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int MAX=1<<30;
typedef struct{ int x; int y; int c;} muchie;

bool operator<(muchie i,muchie j){
    return i.c>j.c;
}

inline muchie mkm(int x,int y,int c){
    muchie mkt;
    mkt.x=x; mkt.y=y; mkt.c=c;
  //  printf("%d %d %d\n",x,y,c);
    return mkt;
}


vector< pair<int,int> > a[200001],arb;
vector<bool> inarb;
vector<int> c;
priority_queue< muchie > q;
int n,ctot=0;

void readGraf(){
    int m;
    freopen("apm.in","r",stdin);
    scanf("%d %d",&n,&m);
    int i,x,y,c;
    for(i=0;i<m;++i){
        scanf("%d %d %d",&x,&y,&c);
        a[x].push_back(make_pair(y,c));
        a[y].push_back(make_pair(x,c));
    }
}

void writeArb(){
    freopen("apm.out","w",stdout);
    printf("%d\n%d\n",ctot,arb.size());
    vector< pair<int,int> >::iterator it;
        for(it=arb.begin();it!=arb.end();++it)
        printf("%d %d\n",it->first,it->second);
}

int main(){
    muchie m;
    readGraf();
    c.resize(n+1);
    c.assign(n+1,MAX);
    inarb.resize(n+1);
    inarb.assign(n+1,false);
    inarb[1]=1;


    vector< pair<int,int> >::iterator it;
    for(it=a[1].begin();it!=a[1].end();++it){
        q.push(mkm(1,it->first,it->second));
        c[it->first]=it->second;
    }
    int y;
    for(int count=1;count<n;++count){
       do{m=q.top();
        q.pop();
       } while(inarb[m.y]);
        arb.push_back(make_pair(m.x,m.y));
        y=m.y;
        inarb[y]=1; ctot+=m.c;
        for(it=a[y].begin();it!=a[y].end();++it) if(!inarb[it->first])
            if(c[it->first]>it->second)
            {
                c[it->first]=it->second;
                q.push(mkm(y,it->first,it->second));
            }
    }
    writeArb();
    return 0;
}