"""simple docstring"""







from collections import deque
def     __UpperCAmelCase							(       UpperCAmelCase_       :							Tuple    )				->     Any:

	'''simple docstring'''





	return input(UpperCAmelCase_    ).strip().split(' '    )
def     __UpperCAmelCase							(       UpperCAmelCase_       :							int     ,				UpperCAmelCase_       :							int    )				->     dict[int, list[int]]:

	'''simple docstring'''





	__snake_case     :				dict[int, list[int]] 						=					{}
	for i in range(UpperCAmelCase_    ):
		__snake_case     :				Any 						=					[]

	for e in range(UpperCAmelCase_    ):
		__snake_case						,							__snake_case     :				Any 						=					(int(UpperCAmelCase_    ) for i in _input(F"Edge {e + 1}: <node1> <node2> "    ))
		graph[x].append(UpperCAmelCase_    )
	return graph
def     __UpperCAmelCase							(       UpperCAmelCase_       :							int     ,				UpperCAmelCase_       :							int    )				->     dict[int, list[int]]:

	'''simple docstring'''





	__snake_case     :				dict[int, list[int]] 						=					{}
	for i in range(UpperCAmelCase_    ):
		__snake_case     :				List[str] 						=					[]

	for e in range(UpperCAmelCase_    ):
		__snake_case						,							__snake_case     :				Optional[Any] 						=					(int(UpperCAmelCase_    ) for i in _input(F"Edge {e + 1}: <node1> <node2> "    ))
		graph[x].append(UpperCAmelCase_    )
		graph[y].append(UpperCAmelCase_    )
	return graph
def     __UpperCAmelCase							(       UpperCAmelCase_       :							int     ,				UpperCAmelCase_       :							int    )				->     dict[int, list[tuple[int, int]]]:

	'''simple docstring'''





	__snake_case     :				dict[int, list[tuple[int, int]]] 						=					{}
	for i in range(UpperCAmelCase_    ):
		__snake_case     :				Dict 						=					[]

	for e in range(UpperCAmelCase_    ):
		__snake_case						,							__snake_case						,							__snake_case     :				List[Any] 						=					(int(UpperCAmelCase_    ) 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__":
	_a,						_a	:	Optional[int]=					(int(i) for i in _input("Number of nodes and edges: "))

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

	_a	:	Optional[int]=					{
	    1: initialize_unweighted_directed_graph,
	    2: initialize_unweighted_undirected_graph,
	    3: initialize_weighted_undirected_graph,
	}[graph_choice](n, m)
def     __UpperCAmelCase							(       UpperCAmelCase_       :							Union[str, Any]     ,				UpperCAmelCase_       :							Optional[int]    )				->     Dict:

	'''simple docstring'''





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

	'''simple docstring'''





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

	'''simple docstring'''





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

	'''simple docstring'''





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

	'''simple docstring'''





	__snake_case     :				str 						=					input().strip()
	__snake_case     :				List[str] 						=					[]
	for _ in range(UpperCAmelCase_    ):
		a.append(map(UpperCAmelCase_     ,				input().strip().split()    )    )
	return a, n
def     __UpperCAmelCase							(       UpperCAmelCase_       :							Tuple    )				->     int:

	'''simple docstring'''





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

	'''simple docstring'''





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

	'''simple docstring'''





	__snake_case						,							__snake_case     :				Union[str, Any] 						=					map(UpperCAmelCase_     ,				input().split(' '    )    )
	__snake_case     :				Dict 						=					[]
	for _ in range(UpperCAmelCase_    ):
		edges.append(map(UpperCAmelCase_     ,				input().split(' '    )    )    )
	return edges, n
def     __UpperCAmelCase							(       UpperCAmelCase_       :							str    )				->     Optional[Any]:

	'''simple docstring'''





	((__snake_case)						,							(__snake_case))     :				int 						=					e_and_n
	e.sort(reverse=UpperCAmelCase_     ,				key=lambda UpperCAmelCase_    : x[2]    )
	__snake_case     :				List[str] 						=					[{i} for i in range(1     ,				n + 1    )]
	while True:
		if len(UpperCAmelCase_    ) == 1:
			break
		print(UpperCAmelCase_    )
		__snake_case     :				List[Any] 						=					e.pop()
		for i in range(len(UpperCAmelCase_    )    ):
			if x[0] in s[i]:
				break
		for j in range(len(UpperCAmelCase_    )    ):
			if x[1] in s[j]:
				if i == j:
					break
				s[j].update(s[i]    )
				s.pop(UpperCAmelCase_    )
				break

def     __UpperCAmelCase							(       UpperCAmelCase_       :							Any    )				->     Optional[int]:

	'''simple docstring'''





	__snake_case     :				Tuple 						=					[]
	for node in graph:
		if not graph[node]:
			isolated.append(UpperCAmelCase_    )
	return isolated






"""simple docstring"""







import dataclasses
import enum
import functools
import math
import re

# The following script is adapted from the script of TaPas.
# Original: https://github.com/google-research/tapas/master/wikisql_utils.py
from typing import Any, List, Text


_a	:	List[Any]=					"none"
_a	:	List[str]=					"none"
def     __UpperCAmelCase							(       UpperCAmelCase_       :							Optional[int]     ,				UpperCAmelCase_       :							Tuple    )				->     Dict:

	'''simple docstring'''





	__snake_case     :				int 						=					value.split(UpperCAmelCase_    )
	return len(UpperCAmelCase_    ) > 1 and any((len(UpperCAmelCase_    ) == 3 for x in split)    )
def     __UpperCAmelCase							(       UpperCAmelCase_       :							Optional[Any]    )				->     Tuple:

	'''simple docstring'''





	if isinstance(UpperCAmelCase_     ,				UpperCAmelCase_    ):
		return value
	if isinstance(UpperCAmelCase_     ,				UpperCAmelCase_    ):
		return float(UpperCAmelCase_    )
	if not isinstance(UpperCAmelCase_     ,				UpperCAmelCase_    ):
		raise ValueError('Argument value is not a string. Can\'t parse it as float'    )
	__snake_case     :				Any 						=					value

	try:
		# Example: 1,000.7
		if "." in sanitized and "," in sanitized:
			return float(sanitized.replace(','     ,				''    )    )
		# 1,000
		if "," in sanitized and _split_thousands(','     ,				UpperCAmelCase_    ):
			return float(sanitized.replace(','     ,				''    )    )
		# 5,5556
		if "," in sanitized and sanitized.count(','    ) == 1 and not _split_thousands(','     ,				UpperCAmelCase_    ):
			return float(sanitized.replace(','     ,				'.'    )    )
		# 0.0.0.1
		if sanitized.count('.'    ) > 1:
			return float(sanitized.replace('.'     ,				''    )    )
		# 0,0,0,1
		if sanitized.count(','    ) > 1:
			return float(sanitized.replace(','     ,				''    )    )
		return float(UpperCAmelCase_    )
	except ValueError:
		# Avoid adding the sanitized value in the error message.
		raise ValueError('Unable to convert value to float'    )
def     __UpperCAmelCase							(       UpperCAmelCase_       :							str    )				->     Any:

	'''simple docstring'''





	if answer is None:
		return None
	try:
		__snake_case     :				Dict 						=					convert_to_float(UpperCAmelCase_    )
		if isinstance(UpperCAmelCase_     ,				UpperCAmelCase_    ) and math.isnan(UpperCAmelCase_    ):
			return None
		return value
	except ValueError:
		return answer.lower()


_a	:	Union[str, Any]=					{
    "text": lambda x: x,
    "real": convert_to_float,
}

class 						UpperCamelCase     (       enum.Enum		):
				UpperCAmelCase							: int       =						0
				UpperCAmelCase							: Optional[Any]       =						1
				UpperCAmelCase							: List[Any]       =						2
				UpperCAmelCase							: Dict       =						3
				UpperCAmelCase							: Union[str, Any]       =						4
				UpperCAmelCase							: int       =						5







class 						UpperCamelCase     (       enum.Enum		):
				UpperCAmelCase							: List[str]       =						0
				UpperCAmelCase							: List[str]       =						1
				UpperCAmelCase							: int       =						2







@dataclasses.dataclass
class 						UpperCamelCase     :
				UpperCAmelCase							: Text
				UpperCAmelCase							: _Operator
				UpperCAmelCase							: Any







_a	:	Union[str, Any]=					re.compile(R"\w+|[^\w\s]+", re.UNICODE | re.MULTILINE | re.DOTALL)
def     __UpperCAmelCase							(       UpperCAmelCase_       :							List[str]    )				->     Optional[Any]:

	'''simple docstring'''





	return list(_TOKENIZER.findall(x.lower()    )    )
def     __UpperCAmelCase							(       UpperCAmelCase_       :							Tuple     ,				UpperCAmelCase_       :							int     ,				UpperCAmelCase_       :							List[Any]    )				->     List[str]:

	'''simple docstring'''





	if operator == _Operator.EQUALS:
		return src == tgt
	elif operator == _Operator.GREATER:
		return src > tgt
	elif operator == _Operator.LESSER:
		return src < tgt
	raise ValueError(F"Unknown operator: {operator}"    )
def     __UpperCAmelCase							(       UpperCAmelCase_       :							List[Any]     ,				UpperCAmelCase_       :							int     ,				UpperCAmelCase_       :							Optional[Any]    )				->     Dict:

	'''simple docstring'''





	__snake_case     :				Optional[Any] 						=					table['types']
	return _TYPE_CONVERTER[types[column]](UpperCAmelCase_    )
def     __UpperCAmelCase							(       UpperCAmelCase_       :							List[Any]    )				->     str:

	'''simple docstring'''





	return isinstance(UpperCAmelCase_     ,				UpperCAmelCase_    )
def     __UpperCAmelCase							(       UpperCAmelCase_       :							Dict     ,				UpperCAmelCase_       :							Union[str, Any]     ,				UpperCAmelCase_       :							int    )				->     List[Any]:

	'''simple docstring'''





	for cond in conditions:
		__snake_case     :				Any 						=					row[cond.column]

		__snake_case     :				Tuple 						=					_parse_value(UpperCAmelCase_     ,				cond.column     ,				cond.cmp_value    )

		if _is_string(UpperCAmelCase_    ) and _is_string(UpperCAmelCase_    ):
			__snake_case     :				str 						=					_normalize_for_match(UpperCAmelCase_    )
			__snake_case     :				Dict 						=					_normalize_for_match(UpperCAmelCase_    )

		if not isinstance(UpperCAmelCase_     ,				type(UpperCAmelCase_    )    ):
			raise ValueError('Type difference {} != {}'.format(type(UpperCAmelCase_    )     ,				type(UpperCAmelCase_    )    )    )

		if not _compare(cond.operator     ,				UpperCAmelCase_     ,				UpperCAmelCase_    ):
			return False
	return True
def     __UpperCAmelCase							(       UpperCAmelCase_       :							Union[str, Any]     ,				UpperCAmelCase_       :							List[str]     ,				UpperCAmelCase_       :							Optional[int]    )				->     Dict:

	'''simple docstring'''





	if not answer_coordinates:
		if aggregation_op == _Aggregation.COUNT:
			return 0.0
		else:
			return EMPTY_ANSWER_AGG

    # Count can support non numeric answers.
	if aggregation_op == _Aggregation.COUNT:
		return float(len(UpperCAmelCase_    )    )

	# If we have just one answer, if float returns it or try a conversion.
	__snake_case     :				Any 						=					[table['rows'][i][j] for (i, j) in answer_coordinates]
	if len(UpperCAmelCase_    ) == 1:
		try:
			return convert_to_float(values[0]    )
		except ValueError as e:
			if aggregation_op != _Aggregation.NONE:
				raise e

	if aggregation_op == _Aggregation.NONE:
		return None

	# Other aggregation only support numeric values. Bail out if we have strings.
	if not all((isinstance(UpperCAmelCase_     ,				(int, float)    ) for v in values)    ):
		return None

	if aggregation_op == _Aggregation.SUM:
		return float(sum(UpperCAmelCase_    )    )
	elif aggregation_op == _Aggregation.AVERAGE:
		return sum(UpperCAmelCase_    ) / len(UpperCAmelCase_    )
	else:
		raise ValueError(F"Unknown aggregation: {aggregation_op}"    )
def     __UpperCAmelCase							(       UpperCAmelCase_       :							Optional[Any]     ,				UpperCAmelCase_       :							int    )				->     str:

	'''simple docstring'''





	__snake_case     :				int 						=					sql_query['agg']
	if aggregation_op_index >= 3:
		__snake_case     :				Optional[Any] 						=					_Aggregation(UpperCAmelCase_    )
	else:
		__snake_case     :				Any 						=					_Aggregation.NONE

	__snake_case     :				Dict 						=					sql_query['sel']
	__snake_case     :				Dict 						=					[
	    _Condition(UpperCAmelCase_     ,				_Operator(UpperCAmelCase_    )     ,				UpperCAmelCase_    )
	    for column, operator, cmp_value in zip(
	        sql_query['conds']['column_index']     ,				sql_query['conds']['operator_index']     ,				sql_query['conds']['condition']    )
	]

	__snake_case     :				str 						=					[]
	for row in range(len(table['rows']    )    ):
		if _respect_conditions(UpperCAmelCase_     ,				table['rows'][row]     ,				UpperCAmelCase_    ):
			indices.append((row, target_column)    )

	if not indices:
		return [], aggregation_op

	if len(UpperCAmelCase_    ) == 1:
		return indices, aggregation_op

	# Parsing of MIN/MAX.
	if aggregation_op_index in (1, 2):
		__snake_case     :				Union[str, Any] 						=					{2: min, 1: max}
		__snake_case     :				Optional[Any] 						=					[(table['rows'][i][j], index) for index, (i, j) in enumerate(UpperCAmelCase_    )]
		__snake_case     :				Tuple 						=					functools.reduce(operators[sql_query['agg']]     ,				UpperCAmelCase_    )

		__snake_case     :				str 						=					[indices[reduced[1]]]
		return ret, _Aggregation.NONE

	return indices, aggregation_op
def     __UpperCAmelCase							(       UpperCAmelCase_       :							Dict     ,				UpperCAmelCase_       :							List[Any]     ,				UpperCAmelCase_       :							Any    )				->     Optional[Any]:

	'''simple docstring'''





	if float_answer is not None:
		return [str(UpperCAmelCase_    )]
	return [str(table['real_rows'][r][c]    ) for r, c in answer_coordinates]

def     __UpperCAmelCase							(       UpperCAmelCase_       :							int     ,				UpperCAmelCase_       :							Tuple    )				->     List:

	'''simple docstring'''





	__snake_case						,							__snake_case     :				List[Any] 						=					_get_answer_coordinates(UpperCAmelCase_     ,				UpperCAmelCase_    )
	__snake_case     :				Optional[int] 						=					_get_float_answer(UpperCAmelCase_     ,				UpperCAmelCase_     ,				UpperCAmelCase_    )
	__snake_case     :				Union[str, Any] 						=					_get_answer_text(UpperCAmelCase_     ,				UpperCAmelCase_     ,				UpperCAmelCase_    )
	# keep the original data the same with TaPas
	if len(UpperCAmelCase_    ) == 0:
		__snake_case     :				List[str] 						=					[EMPTY_ANSWER]
	return answer_text





