#include<stdio.h>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
FILE *f,*g;
int heap[200001],in_g,n,m,weigth;

bool seen[200001];

vector<pair<int,int> > graph[200001],tree;

struct varf{
    int val,heap,varf;
}best[200001];

void swap(int a,int b){
    int aux;
    best[heap[a]].heap=b;
    best[heap[b]].heap=a;
    aux=heap[a];
    heap[a]=heap[b];
    heap[b]=aux;
    
}

void heapify(int i){
    if (2*i<=n){
    int mini=i;
    if (best[heap[i]].val>best[heap[2*i]].val) mini=2*i;
    if (2*i+1<=n && best[heap[mini]].val>best[heap[2*i+1]].val) mini=2*i+1;
    if (mini!=i){
        swap(i,mini);
        heapify(mini);
    }
    }
}

void up_heapify(int i){
    if (i>=2 && best[heap[i/2]].val>best[heap[i]].val){
        swap(i/2,i);
        up_heapify(i/2);
    }
}

void min_heapify(void){
    int i;
    for(i=n/2;i>=1;i--){
        heapify(i);
    }
}

int pop_min(void){
    swap(1,n);
    n--;
    heapify(1);
    return heap[n+1];
}

void add_vertex(void){
    int a;
    a=pop_min();
    seen[a]=1;
    weigth+=best[a].val;
    vector<pair<int, int> >::iterator it=graph[a].begin();
    while(it!=graph[a].end()){
        if (!seen[it->first]){
            if (it->second<best[it->first].val){
                best[it->first].val=it->second;
                up_heapify(best[it->first].heap);
                best[it->first].varf=a;
            }
        
        }
        it++;
    }
    tree.push_back(make_pair(a,best[a].varf));
}

void read(void){
    int i,a,b,w;
    f=fopen("apm.in","r");
    g=fopen("apm.out","w");
    fscanf(f,"%d%d",&n,&m);
    in_g=n-1;
    n--;
    for(i=2;i<=n+1;i++){
        best[i].val=100000;
        best[i].heap=i-1;
        heap[i-1]=i;
    }
    for(i=1;i<=m;i++){
        fscanf(f,"%d%d%d",&a,&b,&w);
        graph[a].push_back(make_pair(b,w));
        graph[b].push_back(make_pair(a,w));
        if (a==1||b==1){
            if (a==1){
                if (best[b].val>w){
                    best[b].val=w;
                    best[b].varf=a;
                    up_heapify(best[b].heap);
                }

            }
            else{
                if (best[a].val>w){
                    best[a].val=w;
                    best[a].varf=b;
                    up_heapify(best[a].heap);
                }
            }
        }
    }

}


int main(void){
    int i;
    read();
    seen[1]=1;
    for(i=1;i<=in_g;i++){
        add_vertex();
    }
    fprintf(g,"%d\n%d\n",weigth,in_g);
    vector<pair<int,int> >::iterator it=tree.begin();
    while(it!=tree.end()){
        fprintf(g,"%d %d\n",it->first,it->second);
        it++;
    }
    return 0;
}