





'''simple docstring'''







from collections import deque





def 							lowerCamelCase_   (	SCREAMING_SNAKE_CASE__   :      Any )			->						List[Any]:
						return input(SCREAMING_SNAKE_CASE__ ).strip().split(''' ''' )





def 							lowerCamelCase_   (	SCREAMING_SNAKE_CASE__   :      int,      SCREAMING_SNAKE_CASE__   :      int )			->						dict[int, list[int]]:
						UpperCAmelCase_      :   dict[int, list[int]]      =	{}
						for i in range(SCREAMING_SNAKE_CASE__ ):
												UpperCAmelCase_      :   Optional[Any]      =	[]

						for e in range(SCREAMING_SNAKE_CASE__ ):
												UpperCAmelCase_    ,							UpperCAmelCase_      :   Union[str, Any]      =	(int(SCREAMING_SNAKE_CASE__ ) for i in _input(F"""Edge {e + 1}: <node1> <node2> """ ))
												graph[x].append(SCREAMING_SNAKE_CASE__ )
						return graph





def 							lowerCamelCase_   (	SCREAMING_SNAKE_CASE__   :      int,      SCREAMING_SNAKE_CASE__   :      int )			->						dict[int, list[int]]:
						UpperCAmelCase_      :   dict[int, list[int]]      =	{}
						for i in range(SCREAMING_SNAKE_CASE__ ):
												UpperCAmelCase_      :   Any      =	[]

						for e in range(SCREAMING_SNAKE_CASE__ ):
												UpperCAmelCase_    ,							UpperCAmelCase_      :   Union[str, Any]      =	(int(SCREAMING_SNAKE_CASE__ ) for i in _input(F"""Edge {e + 1}: <node1> <node2> """ ))
												graph[x].append(SCREAMING_SNAKE_CASE__ )
												graph[y].append(SCREAMING_SNAKE_CASE__ )
						return graph





def 							lowerCamelCase_   (	SCREAMING_SNAKE_CASE__   :      int,      SCREAMING_SNAKE_CASE__   :      int )			->						dict[int, list[tuple[int, int]]]:
						UpperCAmelCase_      :   dict[int, list[tuple[int, int]]]      =	{}
						for i in range(SCREAMING_SNAKE_CASE__ ):
												UpperCAmelCase_      :   str      =	[]

						for e in range(SCREAMING_SNAKE_CASE__ ):
												UpperCAmelCase_    ,							UpperCAmelCase_    ,							UpperCAmelCase_      :   Tuple      =	(int(SCREAMING_SNAKE_CASE__ ) for i in _input(F"""Edge {e + 1}: <node1> <node2> <weight> """ ))
												graph[x].append((y, w) )
												graph[y].append((x, w) )
						return graph


if __name__ == "__main__":
					snake_case_      ,snake_case_  :							Optional[int]            =	(int(i) for i in _input("Number of nodes and edges: "))

					snake_case_  :							Tuple            =	int(
					    _input(
					        "Press 1 or 2 or 3 \n"
					        "1. Unweighted directed \n"
					        "2. Unweighted undirected \n"
					        "3. Weighted undirected \n"
					    )[0]
					)

					snake_case_  :							Union[str, Any]            =	{
					    1: initialize_unweighted_directed_graph,
					    2: initialize_unweighted_undirected_graph,
					    3: initialize_weighted_undirected_graph,
					}[graph_choice](n, m)





def 							lowerCamelCase_   (	SCREAMING_SNAKE_CASE__   :      List[str],      SCREAMING_SNAKE_CASE__   :      Optional[Any] )			->						List[Any]:
						UpperCAmelCase_    ,							UpperCAmelCase_      :   Optional[int]      =	{s}, [s]
						print(SCREAMING_SNAKE_CASE__ )
						while _s:
												UpperCAmelCase_      :   Optional[int]      =	0
												for i in g[_s[-1]]:
																		if i not in vis:
																								_s.append(SCREAMING_SNAKE_CASE__ )
																								vis.add(SCREAMING_SNAKE_CASE__ )
																								UpperCAmelCase_      :   List[Any]      =	1
																								print(SCREAMING_SNAKE_CASE__ )
																								break
												if not flag:
																		_s.pop()





def 							lowerCamelCase_   (	SCREAMING_SNAKE_CASE__   :      Any,      SCREAMING_SNAKE_CASE__   :      int )			->						Union[str, Any]:
						UpperCAmelCase_    ,							UpperCAmelCase_      :   List[str]      =	{s}, deque([s] )
						print(SCREAMING_SNAKE_CASE__ )
						while q:
												UpperCAmelCase_      :   Dict      =	q.popleft()
												for v in g[u]:
																		if v not in vis:
																								vis.add(SCREAMING_SNAKE_CASE__ )
																								q.append(SCREAMING_SNAKE_CASE__ )
																								print(SCREAMING_SNAKE_CASE__ )





def 							lowerCamelCase_   (	SCREAMING_SNAKE_CASE__   :      Dict,      SCREAMING_SNAKE_CASE__   :      List[Any] )			->						Optional[int]:
						UpperCAmelCase_    ,							UpperCAmelCase_    ,							UpperCAmelCase_      :   List[str]      =	{s: 0}, set(), {s: 0}
						while True:
												if len(SCREAMING_SNAKE_CASE__ ) == len(SCREAMING_SNAKE_CASE__ ) - 1:
																		break
												UpperCAmelCase_      :   str      =	100000
												for i in dist:
																		if i not in known and dist[i] < mini:
																								UpperCAmelCase_      :   List[str]      =	dist[i]
																								UpperCAmelCase_      :   Optional[Any]      =	i
												known.add(SCREAMING_SNAKE_CASE__ )
												for v in g[u]:
																		if v[0] not in known and dist[u] + v[1] < dist.get(v[0],      100000 ):
																								UpperCAmelCase_      :   Any      =	dist[u] + v[1]
																								UpperCAmelCase_      :   Tuple      =	u
						for i in dist:
												if i != s:
																		print(dist[i] )





def 							lowerCamelCase_   (	SCREAMING_SNAKE_CASE__   :      List[str],      SCREAMING_SNAKE_CASE__   :      Tuple=None,      SCREAMING_SNAKE_CASE__   :      Dict=None )			->						List[str]:
						if q is None:
												UpperCAmelCase_      :   Optional[Any]      =	[1]
						if ind is None:
												UpperCAmelCase_      :   str      =	[0] * (len(SCREAMING_SNAKE_CASE__ ) + 1)  # SInce oth Index is ignored
												for u in g:
																		for v in g[u]:
																								ind[v] += 1
												UpperCAmelCase_      :   List[Any]      =	deque()
												for i in g:
																		if ind[i] == 0:
																								q.append(SCREAMING_SNAKE_CASE__ )
						if len(SCREAMING_SNAKE_CASE__ ) == 0:
												return
						UpperCAmelCase_      :   List[Any]      =	q.popleft()
						print(SCREAMING_SNAKE_CASE__ )
						for w in g[v]:
												ind[w] -= 1
												if ind[w] == 0:
																		q.append(SCREAMING_SNAKE_CASE__ )
						topo(SCREAMING_SNAKE_CASE__,      SCREAMING_SNAKE_CASE__,      SCREAMING_SNAKE_CASE__ )





def 							lowerCamelCase_   (	)			->						List[str]:
						UpperCAmelCase_      :   Union[str, Any]      =	input().strip()
						UpperCAmelCase_      :   int      =	[]
						for _ in range(SCREAMING_SNAKE_CASE__ ):
												a.append(map(SCREAMING_SNAKE_CASE__,      input().strip().split() ) )
						return a, n





def 							lowerCamelCase_   (	SCREAMING_SNAKE_CASE__   :      Union[str, Any] )			->						Tuple:
						((UpperCAmelCase_)    ,							(UpperCAmelCase_))      :   Union[str, Any]      =	a_and_n
						UpperCAmelCase_      :   int      =	list(SCREAMING_SNAKE_CASE__ )
						UpperCAmelCase_      :   Tuple      =	[[0] * n for i in range(SCREAMING_SNAKE_CASE__ )]
						for k in range(SCREAMING_SNAKE_CASE__ ):
												for i in range(SCREAMING_SNAKE_CASE__ ):
																		for j in range(SCREAMING_SNAKE_CASE__ ):
																								if dist[i][j] > dist[i][k] + dist[k][j]:
																														UpperCAmelCase_      :   Tuple      =	dist[i][k] + dist[k][j]
																														UpperCAmelCase_      :   Union[str, Any]      =	k
						print(SCREAMING_SNAKE_CASE__ )





def 							lowerCamelCase_   (	SCREAMING_SNAKE_CASE__   :      Optional[Any],      SCREAMING_SNAKE_CASE__   :      Any )			->						int:
						UpperCAmelCase_    ,							UpperCAmelCase_    ,							UpperCAmelCase_      :   Any      =	{s: 0}, set(), {s: 0}
						while True:
												if len(SCREAMING_SNAKE_CASE__ ) == len(SCREAMING_SNAKE_CASE__ ) - 1:
																		break
												UpperCAmelCase_      :   Optional[Any]      =	100000
												for i in dist:
																		if i not in known and dist[i] < mini:
																								UpperCAmelCase_      :   Optional[Any]      =	dist[i]
																								UpperCAmelCase_      :   Any      =	i
												known.add(SCREAMING_SNAKE_CASE__ )
												for v in g[u]:
																		if v[0] not in known and v[1] < dist.get(v[0],      100000 ):
																								UpperCAmelCase_      :   List[Any]      =	v[1]
																								UpperCAmelCase_      :   str      =	u
						return dist





def 							lowerCamelCase_   (	)			->						int:
						UpperCAmelCase_    ,							UpperCAmelCase_      :   Any      =	map(SCREAMING_SNAKE_CASE__,      input().split(''' ''' ) )
						UpperCAmelCase_      :   List[str]      =	[]
						for _ in range(SCREAMING_SNAKE_CASE__ ):
												edges.append(map(SCREAMING_SNAKE_CASE__,      input().split(''' ''' ) ) )
						return edges, n





def 							lowerCamelCase_   (	SCREAMING_SNAKE_CASE__   :      Any )			->						Any:
						# Sort edges on the basis of distance
						((UpperCAmelCase_)    ,							(UpperCAmelCase_))      :   Dict      =	e_and_n
						e.sort(reverse=SCREAMING_SNAKE_CASE__,      key=lambda SCREAMING_SNAKE_CASE__ : x[2] )
						UpperCAmelCase_      :   Tuple      =	[{i} for i in range(1,      n + 1 )]
						while True:
												if len(SCREAMING_SNAKE_CASE__ ) == 1:
																		break
												print(SCREAMING_SNAKE_CASE__ )
												UpperCAmelCase_      :   str      =	e.pop()
												for i in range(len(SCREAMING_SNAKE_CASE__ ) ):
																		if x[0] in s[i]:
																								break
												for j in range(len(SCREAMING_SNAKE_CASE__ ) ):
																		if x[1] in s[j]:
																								if i == j:
																														break
																								s[j].update(s[i] )
																								s.pop(SCREAMING_SNAKE_CASE__ )
																								break





def 							lowerCamelCase_   (	SCREAMING_SNAKE_CASE__   :      List[Any] )			->						Any:
						UpperCAmelCase_      :   str      =	[]
						for node in graph:
												if not graph[node]:
																		isolated.append(SCREAMING_SNAKE_CASE__ )
						return isolated










'''simple docstring'''







_UpperCamelCase  						=			{
    "kilogram": 1,
    "gram": pow(10, 3),
    "milligram": pow(10, 6),
    "metric-ton": pow(10, -3),
    "long-ton": 0.0009842073,
    "short-ton": 0.0011023122,
    "pound": 2.2046244202,
    "stone": 0.1574731728,
    "ounce": 35.273990723,
    "carrat": 5000,
    "atomic-mass-unit": 6.0_2213_6652e26,
}

_UpperCamelCase  						=			{
    "kilogram": 1,
    "gram": pow(10, -3),
    "milligram": pow(10, -6),
    "metric-ton": pow(10, 3),
    "long-ton": 1016.04608,
    "short-ton": 907.184,
    "pound": 0.453592,
    "stone": 6.35029,
    "ounce": 0.0283495,
    "carrat": 0.0002,
    "atomic-mass-unit": 1.6_6054_0199e-27,
}
def 			_lowerCAmelCase(      UpperCAmelCase_      :	str					, UpperCAmelCase_      :	str					, UpperCAmelCase_      :	float						) ->							float:
							if to_type not in KILOGRAM_CHART or from_type not in WEIGHT_TYPE_CHART:
														lowerCAmelCase__  =   (
														    F'''Invalid \'from_type\' or \'to_type\' value: {from_type!r}, {to_type!r}\n'''
														    F'''Supported values are: {", ".join(UpperCAmelCase_						)}'''
														)
														raise ValueError(UpperCAmelCase_						)
							return value * KILOGRAM_CHART[to_type] * WEIGHT_TYPE_CHART[from_type]


if __name__ == "__main__":
		import doctest

		doctest.testmod()





