

from collections import deque



def   UpperCamelCase(   lowercase_				)      ->							Any:





  '''simple docstring'''





  return input(lowercase_				).strip().split(""" """				)



def   UpperCamelCase(   lowercase_     ,   lowercase_				)      ->							dict[int, list[int]]:





  '''simple docstring'''





  snake_case_					= {}
  for i in range(lowercase_				):
    snake_case_					= []

  for e in range(lowercase_				):
    snake_case_		,							snake_case_					= (int(lowercase_				) for i in _input(f'''Edge {e + 1}: <node1> <node2> '''				))
    graph[x].append(lowercase_				)
  return graph



def   UpperCamelCase(   lowercase_     ,   lowercase_				)      ->							dict[int, list[int]]:





  '''simple docstring'''





  snake_case_					= {}
  for i in range(lowercase_				):
    snake_case_					= []

  for e in range(lowercase_				):
    snake_case_		,							snake_case_					= (int(lowercase_				) for i in _input(f'''Edge {e + 1}: <node1> <node2> '''				))
    graph[x].append(lowercase_				)
    graph[y].append(lowercase_				)
  return graph



def   UpperCamelCase(   lowercase_     ,   lowercase_				)      ->							dict[int, list[tuple[int, int]]]:





  '''simple docstring'''





  snake_case_					= {}
  for i in range(lowercase_				):
    snake_case_					= []

  for e in range(lowercase_				):
    snake_case_		,							snake_case_		,							snake_case_					= (int(lowercase_				) 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__":
    lowerCamelCase_  ,    lowerCamelCase_					  =   (int(i) for i in _input('''Number of nodes and edges: '''))

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

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



def   UpperCamelCase(   lowercase_     ,   lowercase_				)      ->							Any:





  '''simple docstring'''





  snake_case_		,							snake_case_					= {s}, [s]
  print(lowercase_				)
  while _s:
    snake_case_					= 0
    for i in g[_s[-1]]:
      if i not in vis:
        _s.append(lowercase_				)
        vis.add(lowercase_				)
        snake_case_					= 1
        print(lowercase_				)
        break
    if not flag:
      _s.pop()



def   UpperCamelCase(   lowercase_     ,   lowercase_				)      ->							Tuple:





  '''simple docstring'''





  snake_case_		,							snake_case_					= {s}, deque([s]				)
  print(lowercase_				)
  while q:
    snake_case_					= q.popleft()
    for v in g[u]:
      if v not in vis:
        vis.add(lowercase_				)
        q.append(lowercase_				)
        print(lowercase_				)



def   UpperCamelCase(   lowercase_     ,   lowercase_				)      ->							Union[str, Any]:





  '''simple docstring'''





  snake_case_		,							snake_case_		,							snake_case_					= {s: 0}, set(), {s: 0}
  while True:
    if len(lowercase_				) == len(lowercase_				) - 1:
      break
    snake_case_					= 100000
    for i in dist:
      if i not in known and dist[i] < mini:
        snake_case_					= dist[i]
        snake_case_					= i
    known.add(lowercase_				)
    for v in g[u]:
      if v[0] not in known and dist[u] + v[1] < dist.get(v[0]     ,   100000				):
        snake_case_					= dist[u] + v[1]
        snake_case_					= u
  for i in dist:
    if i != s:
      print(dist[i]				)



def   UpperCamelCase(   lowercase_     ,   lowercase_=None     ,   lowercase_=None				)      ->							Tuple:





  '''simple docstring'''





  if q is None:
    snake_case_					= [1]
  if ind is None:
    snake_case_					= [0] * (len(lowercase_				) + 1)  # SInce oth Index is ignored
    for u in g:
      for v in g[u]:
        ind[v] += 1
    snake_case_					= deque()
    for i in g:
      if ind[i] == 0:
        q.append(lowercase_				)
  if len(lowercase_				) == 0:
    return
  snake_case_					= q.popleft()
  print(lowercase_				)
  for w in g[v]:
    ind[w] -= 1
    if ind[w] == 0:
      q.append(lowercase_				)
  topo(lowercase_     ,   lowercase_     ,   lowercase_				)



def   UpperCamelCase(   )      ->							int:





  '''simple docstring'''





  snake_case_					= input().strip()
  snake_case_					= []
  for _ in range(lowercase_				):
    a.append(map(lowercase_     ,   input().strip().split()				)				)
  return a, n



def   UpperCamelCase(   lowercase_				)      ->							List[Any]:





  '''simple docstring'''





  ((snake_case_)		,							(snake_case_))					= a_and_n
  snake_case_					= list(lowercase_				)
  snake_case_					= [[0] * n for i in range(lowercase_				)]
  for k in range(lowercase_				):
    for i in range(lowercase_				):
      for j in range(lowercase_				):
        if dist[i][j] > dist[i][k] + dist[k][j]:
          snake_case_					= dist[i][k] + dist[k][j]
          snake_case_					= k
  print(lowercase_				)



def   UpperCamelCase(   lowercase_     ,   lowercase_				)      ->							Dict:





  '''simple docstring'''





  snake_case_		,							snake_case_		,							snake_case_					= {s: 0}, set(), {s: 0}
  while True:
    if len(lowercase_				) == len(lowercase_				) - 1:
      break
    snake_case_					= 100000
    for i in dist:
      if i not in known and dist[i] < mini:
        snake_case_					= dist[i]
        snake_case_					= i
    known.add(lowercase_				)
    for v in g[u]:
      if v[0] not in known and v[1] < dist.get(v[0]     ,   100000				):
        snake_case_					= v[1]
        snake_case_					= u
  return dist



def   UpperCamelCase(   )      ->							Dict:





  '''simple docstring'''





  snake_case_		,							snake_case_					= map(lowercase_     ,   input().split(""" """				)				)
  snake_case_					= []
  for _ in range(lowercase_				):
    edges.append(map(lowercase_     ,   input().split(""" """				)				)				)
  return edges, n



def   UpperCamelCase(   lowercase_				)      ->							Tuple:





  '''simple docstring'''





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



def   UpperCamelCase(   lowercase_				)      ->							List[str]:





  '''simple docstring'''





  snake_case_					= []
  for node in graph:
    if not graph[node]:
      isolated.append(lowercase_				)
  return isolated


def   UpperCamelCase(   lowercase_				)      ->							float:





  '''simple docstring'''





  return -num if num < 0 else num



def   UpperCamelCase(   lowercase_				)      ->							int:





  '''simple docstring'''





  if len(lowercase_				) == 0:
    raise ValueError("""abs_min() arg is an empty sequence"""				)
  snake_case_					= x[0]
  for i in x:
    if abs_val(lowercase_				) < abs_val(lowercase_				):
      snake_case_					= i
  return j



def   UpperCamelCase(   lowercase_				)      ->							int:





  '''simple docstring'''





  if len(lowercase_				) == 0:
    raise ValueError("""abs_max() arg is an empty sequence"""				)
  snake_case_					= x[0]
  for i in x:
    if abs(lowercase_				) > abs(lowercase_				):
      snake_case_					= i
  return j



def   UpperCamelCase(   lowercase_				)      ->							int:





  '''simple docstring'''





  if len(lowercase_				) == 0:
    raise ValueError("""abs_max_sort() arg is an empty sequence"""				)
  return sorted(lowercase_     ,   key=lowercase_				)[-1]



def   UpperCamelCase(   )      ->							List[Any]:





  '''simple docstring'''





  assert abs_val(0				) == 0
  assert abs_val(34				) == 34
  assert abs_val(-100000000000				) == 100000000000

  snake_case_					= [-3, -1, 2, -11]
  assert abs_max(lowercase_				) == -11
  assert abs_max_sort(lowercase_				) == -11
  assert abs_min(lowercase_				) == -1


if __name__ == "__main__":
    import doctest

    doctest.testmod()

    test_abs_val()
    print(abs_val(-34))  # --> 34