#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; 

int VEC[maxn],ANS,V[maxn],H[maxn * 2 + 100],POZ[maxn]; 
vector <pair<int,int> > VECT[maxn],VANS; 
int N,M,L,C[maxn]; 

void introduce_in_apm(int x) 
{ 
    
for(unsigned int i = 0;i < VECT[x].size(); ++i)     
{         
int nod = VECT[x][i].first;         
int cost = VECT[x][i].second;         
V[nod] = min(V[nod],cost);         
if (V[nod] == cost) VEC[nod] = x;     
} 
} 

void push(int poz) 
{    
while((poz * 2 <= L && V[H[poz]] > V[H[poz * 2]]) || (poz * 2 + 1 <= L && V[H[poz]] > V[H[poz * 2 + 1]]))     
{         
if (V[H[poz * 2]] < V[H[poz * 2 + 1]] || poz * 2 + 1 > L)                  
{             
swap(H[poz],H[poz * 2]);           
swap(POZ[H[poz]],POZ[H[poz * 2]]);             
poz *= 2; 
} 
else         
{             
swap(H[poz],H[poz * 2 + 1]);             
swap(POZ[H[poz]],POZ[H[poz * 2 + 1]]);             
poz = poz * 2 + 1;         
}     
} 
}  
void pop(int poz) 
{ 
{        
swap(H[poz],H[poz / 2]);         
swap(POZ[H[poz]],POZ[H[poz / 2]]); 
poz = poz / 2; 
} 
} 

void introduce_in_heap(int nod) 
{ 
   
H[++L] = nod;     
POZ[nod] = L;     
pop(L); 
 

int scoate_radacina_heap() 
{     
int x = H[1];     
swap(H[1],H[L]);     
swap(POZ[H[1]],POZ[H[L]]);    
L--;     
push(1);         
POZ[x] = 0;     
return x; 
} 
int main() 
{     
freopen("apm.in","r",stdin);    
freopen("apm.out","w",stdout);     
scanf("%d %d\n",&N,&M);     
for(int i = 1;i <= M; ++i)    
{         
int x,y,c;         
scanf("%d %d %d",&x,&y,&c);    
VECT[x].pb(mkp(y,c));        
VECT[y].pb(mkp(x,c));     
}    
for(int i = 1;i <= N; ++i) V[i] = INF;    
V[1] = 0;   
introduce_in_apm(1);     
for(int i = 2;i <= N; ++i)             
introduce_in_heap(i);          
for(int i = 1;i < N; ++i)   
{         
int x = scoate_radacina_heap();        
introduce_in_apm(x);         
ANS += V[x];         
VANS.pb(mkp(x,VEC[x]));         
for(unsigned int j = 0;j < VECT[x].size(); ++j)        
{             
int nod = VECT[x][j].first;             
if (POZ[nod]) 
pop(POZ[nod]);       
}     
}    
printf("%d\n",ANS);    
printf("%d\n",N-1);     
for(unsigned int i = 0;i < N - 1; ++i)        
printf("%d %d\n",VANS[i].first,VANS[i].second);    
return 0; 
}