#include <bits/stdc++.h>
#define MAX (int)(2e5+5)
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
typedef pair<int,int> PairInt;
struct muchie{
    PairInt nod;
    int cost;
    bool operator< (const muchie& other) const{
        return cost > other.cost;
    }
};

int n,S;
bool Intalnit[MAX];
priority_queue <muchie> Pq;
vector <PairInt> Nod[MAX];
stack <PairInt> Ans;

void citire();
void rezolvare();
void afisare();

int main(){
    citire();
    rezolvare();
    afisare();
    return 0;
}
void rezolvare(){
    int i,x,sz;
    muchie t;
    sz=Nod[1].size();
    Intalnit[1]=1;
    for(i=0;i<sz;++i)
        Pq.push( {make_pair(1,Nod[1][i].first),Nod[1][i].second} );
    while(!Pq.empty()){
        t=Pq.top();
        Pq.pop();
        x=t.nod.second;
        if(Intalnit[x])
            continue;
        Intalnit[x]=1;
        S+=t.cost;
        Ans.push(make_pair(t.nod.first,t.nod.second));

        sz=Nod[x].size();
        for(i=0;i<sz;++i)
            if(!Intalnit[Nod[x][i].first])
                Pq.push( {make_pair(x,Nod[x][i].first), Nod[x][i].second} );

    }
}
void afisare(){
    int i;
    fout<<S<<'\n'<<Ans.size()<<'\n';
    while(!Ans.empty()){
        fout<<Ans.top().first<<' '<<Ans.top().second<<'\n';
        Ans.pop();
    }
}
void citire(){
    int i,m,x,y,c;
    fin>>n>>m;
    for(i=0;i<m;++i){
        fin>>x>>y>>c;
        Nod[x].push_back(make_pair(y,c));
        Nod[y].push_back(make_pair(x,c));
    }
}