

"""simple docstring"""


from collections import deque






def 					a__					(					__SCREAMING_SNAKE_CASE				)			->			Dict:
		return input(__SCREAMING_SNAKE_CASE				).strip().split(" "				)






def 					a__					(					__SCREAMING_SNAKE_CASE      ,				__SCREAMING_SNAKE_CASE				)			->			dict[int, list[int]]:
		__lowerCAmelCase: dict[int, list[int]]					   =    {}
		for i in range(__SCREAMING_SNAKE_CASE				):
				__lowerCAmelCase: Dict					   =    []

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






def 					a__					(					__SCREAMING_SNAKE_CASE      ,				__SCREAMING_SNAKE_CASE				)			->			dict[int, list[int]]:
		__lowerCAmelCase: dict[int, list[int]]					   =    {}
		for i in range(__SCREAMING_SNAKE_CASE				):
				__lowerCAmelCase: Optional[int]					   =    []

		for e in range(__SCREAMING_SNAKE_CASE				):
				__lowerCAmelCase   ,				__lowerCAmelCase: str					   =    (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 					a__					(					__SCREAMING_SNAKE_CASE      ,				__SCREAMING_SNAKE_CASE				)			->			dict[int, list[tuple[int, int]]]:
		__lowerCAmelCase: dict[int, list[tuple[int, int]]]					   =    {}
		for i in range(__SCREAMING_SNAKE_CASE				):
				__lowerCAmelCase: int					   =    []

		for e in range(__SCREAMING_SNAKE_CASE				):
				__lowerCAmelCase   ,				__lowerCAmelCase   ,				__lowerCAmelCase: Union[str, Any]					   =    (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__":
			__A     ,       __A		     =    (int(i) for i in _input("Number of nodes and edges: "))

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

			__A		     =    {
			    1: initialize_unweighted_directed_graph,
			    2: initialize_unweighted_undirected_graph,
			    3: initialize_weighted_undirected_graph,
			}[graph_choice](n, m)






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






def 					a__					(					__SCREAMING_SNAKE_CASE      ,				__SCREAMING_SNAKE_CASE				)			->			Dict:
		__lowerCAmelCase   ,				__lowerCAmelCase: str					   =    {s}, deque([s]				)
		print(__SCREAMING_SNAKE_CASE				)
		while q:
				__lowerCAmelCase: Union[str, Any]					   =    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 					a__					(					__SCREAMING_SNAKE_CASE      ,				__SCREAMING_SNAKE_CASE				)			->			List[Any]:
		__lowerCAmelCase   ,				__lowerCAmelCase   ,				__lowerCAmelCase: str					   =    {s: 0}, set(), {s: 0}
		while True:
				if len(__SCREAMING_SNAKE_CASE				) == len(__SCREAMING_SNAKE_CASE				) - 1:
						break
				__lowerCAmelCase: Union[str, Any]					   =    1_0_0_0_0_0
				for i in dist:
						if i not in known and dist[i] < mini:
								__lowerCAmelCase: Optional[int]					   =    dist[i]
								__lowerCAmelCase: Tuple					   =    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]      ,				1_0_0_0_0_0				):
								__lowerCAmelCase: Dict					   =    dist[u] + v[1]
								__lowerCAmelCase: str					   =    u
		for i in dist:
				if i != s:
						print(dist[i]				)






def 					a__					(					__SCREAMING_SNAKE_CASE      ,				__SCREAMING_SNAKE_CASE=None      ,				__SCREAMING_SNAKE_CASE=None				)			->			Optional[Any]:
		if q is None:
				__lowerCAmelCase: List[Any]					   =    [1]
		if ind is None:
				__lowerCAmelCase: Optional[int]					   =    [0] * (len(__SCREAMING_SNAKE_CASE				) + 1)  # SInce oth Index is ignored
				for u in g:
						for v in g[u]:
								ind[v] += 1
				__lowerCAmelCase: List[Any]					   =    deque()
				for i in g:
						if ind[i] == 0:
								q.append(__SCREAMING_SNAKE_CASE				)
		if len(__SCREAMING_SNAKE_CASE				) == 0:
				return
		__lowerCAmelCase: 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 					a__					(					)			->			Tuple:
		__lowerCAmelCase: Tuple					   =    input().strip()
		__lowerCAmelCase: List[Any]					   =    []
		for _ in range(__SCREAMING_SNAKE_CASE				):
				a.append(map(__SCREAMING_SNAKE_CASE      ,				input().strip().split()				)				)
		return a, n






def 					a__					(					__SCREAMING_SNAKE_CASE				)			->			Optional[Any]:
		((__lowerCAmelCase)   ,				(__lowerCAmelCase)): int					   =    a_and_n
		__lowerCAmelCase: str					   =    list(__SCREAMING_SNAKE_CASE				)
		__lowerCAmelCase: int					   =    [[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]:
										__lowerCAmelCase: List[Any]					   =    dist[i][k] + dist[k][j]
										__lowerCAmelCase: Optional[Any]					   =    k
		print(__SCREAMING_SNAKE_CASE				)






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






def 					a__					(					)			->			str:
		__lowerCAmelCase   ,				__lowerCAmelCase: str					   =    map(__SCREAMING_SNAKE_CASE      ,				input().split(" "				)				)
		__lowerCAmelCase: Union[str, Any]					   =    []
		for _ in range(__SCREAMING_SNAKE_CASE				):
				edges.append(map(__SCREAMING_SNAKE_CASE      ,				input().split(" "				)				)				)
		return edges, n






def 					a__					(					__SCREAMING_SNAKE_CASE				)			->			Tuple:
		# Sort edges on the basis of distance
		((__lowerCAmelCase)   ,				(__lowerCAmelCase)): str					   =    e_and_n
		e.sort(reverse=__SCREAMING_SNAKE_CASE      ,				key=lambda __SCREAMING_SNAKE_CASE				: x[2]				)
		__lowerCAmelCase: List[str]					   =    [{i} for i in range(1      ,				n + 1				)]
		while True:
				if len(__SCREAMING_SNAKE_CASE				) == 1:
						break
				print(__SCREAMING_SNAKE_CASE				)
				__lowerCAmelCase: List[Any]					   =    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 					a__					(					__SCREAMING_SNAKE_CASE				)			->			Optional[Any]:
		__lowerCAmelCase: Optional[Any]					   =    []
		for node in graph:
				if not graph[node]:
						isolated.append(__SCREAMING_SNAKE_CASE				)
		return isolated





"""simple docstring"""


def 					a__					(					__SCREAMING_SNAKE_CASE = 1_0_0_0				)			->			int:
		__lowerCAmelCase: int					   =    0
		__lowerCAmelCase: Optional[int]					   =    0
		while 1:
				num += 3
				if num >= n:
						break
				total += num
				num += 2
				if num >= n:
						break
				total += num
				num += 1
				if num >= n:
						break
				total += num
				num += 3
				if num >= n:
						break
				total += num
				num += 1
				if num >= n:
						break
				total += num
				num += 2
				if num >= n:
						break
				total += num
				num += 3
				if num >= n:
						break
				total += num
		return total


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


