#include<cstdio>
#include<vector>
using namespace std;
const int Nmax = 200001;
const int Mmax = 400001;
struct item{
    int node,cost;
    item(){} item(int _x,int _y){node=_x,cost=_y;}
};
int N,M;
vector<int> G[Nmax],C[Nmax];
int 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){
        if(wh[x]){
            if(c<A[wh[x]].cost){
                A[wh[x]].cost=c;
                upheap(wh[x]);
            }
        }
        else{
            A[++K]=item(x,c);
            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(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d\n",&N,&M);
    int x,y,c;
    for(int i=1;i<=M;i++){
        scanf("%d %d %d",&x,&y,&c);
        G[x].push_back(y);
        G[y].push_back(x);
        C[x].push_back(c);
        C[y].push_back(c);
    }
    mark[1]=1;
    for(int i=0;i<G[1].size();i++) H.push(G[1][i],C[1][i]);
    while(!H.empty()){
        item p=H.front(); H.pop();
        sol+=p.cost;
        mark[p.node]=1;
        for(int i=0;i<G[p.node].size();i++){
            if(!mark[G[p.node][i]]){
                H.push(G[p.node][i],C[p.node][i]);
            }
            else if(mark[p.node]==1 && C[p.node][i]==p.cost){
                X[++X[0]]=G[p.node][i],Y[X[0]]=p.node;
                mark[p.node]=2;
            }
        }
    }
    printf("%d\n%d\n",sol,N-1);
    for(int i=1;i<=N;i++) printf("%d %d\n",X[i],Y[i]);
    return 0;
}