#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int Nmax = 200001;
const int Mmax = 400001;
struct item{
    int node,cost,org;
    item(){} item(int _x,int _y,int _z){node=_x,cost=_y,org=_z;}
};
int N,M;
int Prev[Mmax],Cost[Mmax],To[Mmax],el;
int Last[Nmax],mark[Nmax];
class Heap{
    private:
    item A[Nmax];
    int wh[Nmax],K;
    void upheap(int i){
        if(i/2>=1 && A[i/2].cost > A[i].cost){
            swap(wh[A[i/2].node],wh[A[i].node]);
            swap(A[i/2],A[i]);
            upheap(i/2);
        }
    }
    void downheap(int i){
        if(2*i+1<=K && A[2*i+1].cost<A[i].cost && A[2*i+1].cost<=A[2*i].cost){
            swap(wh[A[2*i+1].node],wh[A[i].node]);
            swap(A[2*i+1],A[i]);
            downheap(2*i+1);
        }
        else if(2*i<=K && A[2*i].cost<A[i].cost){
            swap(wh[A[2*i].node],wh[A[i].node]);
            swap(A[2*i],A[i]);
            downheap(2*i);
        }
    }
    public:
    void push(int &x,int &c,int fr){
        if(wh[x]){
            if(c<A[wh[x]].cost){
                A[wh[x]].cost=c;
                A[wh[x]].org=fr;
                upheap(wh[x]);
            }
        }
        else{
            A[++K]=item(x,c,fr);
            wh[x]=K;
            upheap(K);
        }
    }
    void pop(){
        swap(wh[A[1].node],wh[A[K].node]);
        swap(A[1],A[K]);
        wh[A[K].node]=0;
        K--;
        downheap(1);
    }
    bool empty(){
        return K==0;
    }
    item front(){
        return A[1];
    }
} H;
int X[Nmax],Y[Nmax],sol;
int main(){
    in>>N>>M;
    int x,y,c;
    for(int i=1;i<=M;i++){
        in>>x>>y>>c;
        To[++el]=y, Cost[el]=c, Prev[el]=Last[x], Last[x]=el;
        To[++el]=x, Cost[el]=c, Prev[el]=Last[y], Last[y]=el;
    }
    mark[1]=1;
    for(int i=Last[1];i;i=Prev[i]) H.push(To[i],Cost[i],1);
    while(!H.empty()){
        item p=H.front(); H.pop();
        sol+=p.cost;
        X[++X[0]]=p.org,Y[X[0]]=p.node;
        mark[p.node]=1;

        for(int i=Last[p.node];i;i=Prev[i]){
            if(!mark[To[i]]) H.push(To[i],Cost[i],p.node);
        }
    }
    out<<sol<<'\n'<<N-1<<'\n';
    for(int i=1;i<=N-1;i++) out<<X[i]<<' '<<Y[i]<<'\n';
    return 0;
}