#include<stdio.h> 
#include<algorithm> 
#include<vector> 
#include<fstream>
#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) 
{ 
    
while(poz > 1 && V[H[poz]] < V[H[poz / 2]]) 
  
{ 
        
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("retea.in","r",stdin); 
   
int k;
scanf("%d %d %d\n",&N,&M,&k); 
  
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]); 
      
} 
    
} 
   

ofstream fout("retea.out");
fout<<ANS<<' ';
for(unsigned int i = 0;i < N - 1; ++i) 
	fout<<VANS[i].first<<' '<<VANS[i].second<<' '<<VECT[i].pb(mkp(i,c)) <<'\n'; 
fout.close(); 
    

   
return 0; 
}