#include <stdio.h> 
#include<algorithm>
#include<vector>
#define pb push_back
#define mkp make_pair

using namespace std;
const int maxn = 200200;
const int INF = 200000200;

const int MAX_HEAP_SIZE = 16384;
typedef int Heap[MAX_HEAP_SIZE];

 vector < pair<int,int> > a[maxn]; 
int N,N1=0 ,M,N2=0;
Heap H;
int V[maxn],Poz[maxn],F[maxn];



void adauga(int a1, int b, int c){
     a[a1].pb(mkp(b,c)); 
}
 inline int father(int nod) {
    return nod / 2;
}
 
inline int left_son(int nod) {
    return nod * 2;
}
 
inline int right_son(int nod) {
    return nod * 2 + 1;
}
 void sift(Heap H, int N1, int K) {
    int son=1;
     while (son>0){
        son = 0;
        // Alege un fiu mai mare ca tatal.
        if (left_son(K) <= N1) {
            son = left_son(K);
            if (right_son(K) <= N1 && V[H[right_son(K)]] < V[H[left_son(K)]]) {
                son = right_son(K);
            }
            if (V[H[son]] >= V[H[K]]) {
                son = 0;
            }
        }
 
        if (son) {
        	swap(Poz[H[K]],Poz[H[son]]);
            std::swap(H[K], H[son]);  // Functie STL ce interschimba H[K] cu H[son].
            K = son;
        }
    } ;
}

void percolate(Heap H, int N1, int K) {
   
 
    while ((K > 1) && (V[H[K]] < V[H[father(K)]])) {
        swap(Poz[H[K]],Poz[H[father(K)]]);
        swap(H[K],H[father(K)]);        
        K = father(K);
    }
 
    
}

void cut(Heap H, int& N1, int K) {
	Poz[H[N1]]=K;
    swap(H[K] ,H[N1]);
    --N1;
 
 
    if ((K > 1) && (V[H[K]] < V[H[father(K)]])) {
        percolate(H, N1, K);
    } else {
        sift(H, N1, K);
    }
}

void change(Heap H, int& N1, int K, int key,int f) {
//	Poz[H[N1]]=K;
  //  swap(H[K] ,H[N1]);
  //  --N1;
  V[K]=key;
  F[K]=f;
  K=Poz[K];
  
 
    if ((K > 1) && (V[H[K]] < V[H[father(K)]])) {
        percolate(H, N1, K);
    } else {
        sift(H, N1, K);
    }
}

void insert(Heap H, int& N1, int key) {
	V[++N2] = key;
    H[++N1] = N2;
    Poz[N2] = N1;
    percolate(H, N1, N1);
}
 
 
int main()
{
      freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
 
    int i,a1,b,c,s=0;
    
    
    scanf("%d %d ", &N, &M);
    for(i=1;i<=M;++i){
    	scanf("%d %d %d ", &a1, &b, &c);
    	adauga(a1,b,c);
    	adauga(b,a1,c);
    }
    for(int j=1;j<=N;++j){
    for(unsigned int i = 0;i < a[j].size(); ++i)
    {	
    //	printf("%d ", a[j][i].second);
    }
   // printf("\n");
}
  insert(H,N1,-INF);
 for(i=2;i<=N;i++){
 	insert(H,N1,INF);
 	F[i]=0;
 }
 
 while(N1>0){
  	i=H[1];
  	if(V[i]!=-INF)s+=V[i];
  	cut(H,N1,1);V[i] = -INF;
  	for(int j=0;j<a[i].size();j++){
  		int nod = a[i][j].first;
  		if(a[i][j].second < V[nod])change(H,N1,nod,a[i][j].second,i);
  	}
  	
    
  }

  
    printf("%d\n", s);
    printf("%d\n", N-1);
    for(i=2;i<=N;i++){
     printf("%d %d\n", i,F[i]);
  }
 
    return 0;
}