#include<stdio.h>
#include<algorithm>
#include<vector>

const int maxn=200002;
const int maxm=400002;

typedef struct muchie{
    int x,y;
    int cost;
    void add(int x,int y,int cost){
        this->x=x;
        this->y=y;
        this->cost=cost;
    }
} Muchie;

int N,M;
int rad[maxn];
Muchie graph[maxm];
std::vector<int> sol;

bool comp(muchie a,muchie b){
    return a.cost<b.cost;
}

int _find(int x){
    while(rad[x]!=x)
        x=rad[x];
    return x;
}

void _merge(int nr,int tata){
    if(rad[nr]!=nr){
        _merge(rad[nr],tata);
    }
    rad[nr]=tata;
}

int main(){
	int i,x,y,cost;
    int nr=0,totalcost=0;

    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&N,&M);

    for(i=0;i<M;i++){
        scanf("%d %d %d",&x,&y,&cost);
        graph[i].add(x,y,cost);
    }

    std::sort(graph,graph+M,comp);
    for(i=1;i<=N;i++)
        rad[i]=i;

    for(i=0;(nr<N-1 && i<M);i++){
        x=_find(graph[i].x);
        y=_find(graph[i].y);
        if(x!=y){
            _merge(graph[i].y,x);

            totalcost+=graph[i].cost;
            sol.push_back(i);
            nr++;
        }
    }
    printf("%d\n%d\n",totalcost,N-1);
    for(unsigned int i=0;i<sol.size();i++){
        printf("%d %d\n",graph[sol[i]].x,graph[sol[i]].y);
    }

    return 0;
}