






import heapq as hq
import math
from collections.abc import Iterator




class 							snake_case_       :

						"""simple docstring"""



						def __init__(self:					List[str] ,					__UpperCAmelCase:					int   )    ->     Dict:




											'''simple docstring'''



											__a					:						List[Any]      =					str(id_   )
											__a					:						Union[str, Any]      =					None
											__a					:						str      =					None
											__a					:						Union[str, Any]      =					[]
											__a					:						List[str]      =					{}  # {vertex:distance}



						def __lt__(self:					List[str] ,					__UpperCAmelCase:					Union[str, Any]   )    ->     Optional[int]:




											'''simple docstring'''



											return self.key < other.key



						def __repr__(self:					int   )    ->     Union[str, Any]:




											'''simple docstring'''



											return self.id



						def        UpperCAmelCase__					(self:					Dict ,					__UpperCAmelCase:					Union[str, Any]   )    ->     Dict:




											'''simple docstring'''



											self.neighbors.append(__UpperCAmelCase   )



						def        UpperCAmelCase__					(self:					Optional[int] ,					__UpperCAmelCase:					str ,					__UpperCAmelCase:					Tuple   )    ->     Dict:




											'''simple docstring'''



											__a					:						int      =					weight







def     a_   (__A				,       __A				,       __A				,       __A      )				->						Tuple:



					"""simple docstring"""
					# add the neighbors:
					graph[a - 1].add_neighbor(graph[b - 1]      )
					graph[b - 1].add_neighbor(graph[a - 1]      )
					# add the edges:
					graph[a - 1].add_edge(graph[b - 1]				,       lowerCamelCase_      )
					graph[b - 1].add_edge(graph[a - 1]				,       lowerCamelCase_      )







def     a_   (__A				,       __A      )				->						Union[str, Any]:



					"""simple docstring"""
					__a					:						int      =					[]
					for u in graph:
										__a					:						Optional[int]      =					math.inf
										__a					:						List[str]      =					None
					__a					:						Any      =					0
					__a					:						Any      =					graph[:]
					while q:
										__a					:						int      =					min(lowerCamelCase_      )
										q.remove(lowerCamelCase_      )
										for v in u.neighbors:
															if (v in q) and (u.edges[v.id] < v.key):
																				__a					:						List[str]      =					u
																				__a					:						List[Any]      =					u.edges[v.id]
					for i in range(1				,       len(lowerCamelCase_      )      ):
										a.append((int(graph[i].id      ) + 1, int(graph[i].pi.id      ) + 1)      )
					return a







def     a_   (__A				,       __A      )				->						Tuple:



					"""simple docstring"""
					for u in graph:
										__a					:						Any      =					math.inf
										__a					:						Dict      =					None
					__a					:						Tuple      =					0

					__a					:						int      =					list(lowerCamelCase_      )
					hq.heapify(lowerCamelCase_      )

					while h:
										__a					:						Optional[Any]      =					hq.heappop(lowerCamelCase_      )
										for v in u.neighbors:
															if (v in h) and (u.edges[v.id] < v.key):
																				__a					:						List[str]      =					u
																				__a					:						Dict      =					u.edges[v.id]
																				hq.heapify(lowerCamelCase_      )

					for i in range(1				,       len(lowerCamelCase_      )      ):
										yield (int(graph[i].id      ) + 1, int(graph[i].pi.id      ) + 1)







def     a_   ()				->						List[str]:



					"""simple docstring"""
					pass


if __name__ == "__main__":
			import doctest

			doctest.testmod()








def        snake_case__		(    lowerCamelCase_ = 1000		):
							return sum(e for e in range(3     ,				lowerCamelCase_		) if e % 3 == 0 or e % 5 == 0		)


if __name__ == "__main__":
		print(F"{solution() = }")






