'''simple docstring'''


from collections import deque


def 					_lowerCamelCase    (      lowerCamelCase_					:							Tuple   ):



     """simple docstring"""





     return input(lowerCamelCase_   ).strip().split(' '   )


def 					_lowerCamelCase    (      lowerCamelCase_					:							int	,     lowerCamelCase_					:							int   ):



     """simple docstring"""





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

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


def 					_lowerCamelCase    (      lowerCamelCase_					:							int	,     lowerCamelCase_					:							int   ):



     """simple docstring"""





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

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


def 					_lowerCamelCase    (      lowerCamelCase_					:							int	,     lowerCamelCase_					:							int   ):



     """simple docstring"""





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

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

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

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


def 					_lowerCamelCase    (      lowerCamelCase_					:							List[Any]	,     lowerCamelCase_					:							Any   ):



     """simple docstring"""





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


def 					_lowerCamelCase    (      lowerCamelCase_					:							Union[str, Any]	,     lowerCamelCase_					:							List[Any]   ):



     """simple docstring"""





     UpperCAmelCase_   ,			UpperCAmelCase_							:   Optional[int]   =      {s}, deque([s]   )
     print(lowerCamelCase_   )
     while q:
          UpperCAmelCase_							:   Tuple   =      q.popleft()
          for v in g[u]:
               if v not in vis:
                    vis.add(lowerCamelCase_   )
                    q.append(lowerCamelCase_   )
                    print(lowerCamelCase_   )


def 					_lowerCamelCase    (      lowerCamelCase_					:							Any	,     lowerCamelCase_					:							int   ):



     """simple docstring"""





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


def 					_lowerCamelCase    (      lowerCamelCase_					:							Dict	,     lowerCamelCase_					:							List[str]=None	,     lowerCamelCase_					:							Dict=None   ):



     """simple docstring"""





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


def 					_lowerCamelCase    (      ):



     """simple docstring"""





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


def 					_lowerCamelCase    (      lowerCamelCase_					:							Any   ):



     """simple docstring"""





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


def 					_lowerCamelCase    (      lowerCamelCase_					:							List[str]	,     lowerCamelCase_					:							List[Any]   ):



     """simple docstring"""





     UpperCAmelCase_   ,			UpperCAmelCase_   ,			UpperCAmelCase_							:   Any   =      {s: 0}, set(), {s: 0}
     while True:
          if len(lowerCamelCase_   ) == len(lowerCamelCase_   ) - 1:
               break
          UpperCAmelCase_							:   List[str]   =      100000
          for i in dist:
               if i not in known and dist[i] < mini:
                    UpperCAmelCase_							:   Any   =      dist[i]
                    UpperCAmelCase_							:   List[Any]   =      i
          known.add(lowerCamelCase_   )
          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_							:   Dict   =      u
     return dist


def 					_lowerCamelCase    (      ):



     """simple docstring"""





     UpperCAmelCase_   ,			UpperCAmelCase_							:   Union[str, Any]   =      map(lowerCamelCase_	,     input().split(' '   )   )
     UpperCAmelCase_							:   str   =      []
     for _ in range(lowerCamelCase_   ):
          edges.append(map(lowerCamelCase_	,     input().split(' '   )   )   )
     return edges, n


def 					_lowerCamelCase    (      lowerCamelCase_					:							List[Any]   ):



     """simple docstring"""





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





def 					_lowerCamelCase    (      lowerCamelCase_					:							Dict   ):



     """simple docstring"""





     UpperCAmelCase_							:   Optional[Any]   =      []
     for node in graph:
          if not graph[node]:
               isolated.append(lowerCamelCase_   )
     return isolated







'''simple docstring'''


from __future__ import annotations

from collections import deque
from enum import Enum
from math import atana, degrees
from sys import maxsize






class      __SCREAMING_SNAKE_CASE						(       lowerCamelCase_       ):







  '''simple docstring'''






  lowerCamelCase_		:Union[str, Any]						    =		1
  lowerCamelCase_		:List[Any]						    =		2
  lowerCamelCase_		:Optional[Any]						    =		3


  def __repr__( self						):




       '''simple docstring'''

       return F'''{self.__class__.__name__}.{self.name}'''







def 					_lowerCamelCase    (      lowerCamelCase_					:							tuple[int, int]	,     lowerCamelCase_					:							int	,     lowerCamelCase_					:							int   ):



     """simple docstring"""





     UpperCAmelCase_   ,			UpperCAmelCase_							:   Any   =      point
     return degrees(atana(y - miny	,     x - minx   )   )


def 					_lowerCamelCase    (      lowerCamelCase_					:							tuple[int, int]	,     lowerCamelCase_					:							tuple[int, int]	,     lowerCamelCase_					:							tuple[int, int]   ):



     """simple docstring"""





     UpperCAmelCase_   ,			UpperCAmelCase_							:   str   =      starting
     UpperCAmelCase_   ,			UpperCAmelCase_							:   Optional[int]   =      via
     UpperCAmelCase_   ,			UpperCAmelCase_							:   Dict   =      target
     UpperCAmelCase_							:   Optional[Any]   =      degrees(atana(ya - ya	,     xa - xa   )   )
     via_angle %= 360
     UpperCAmelCase_							:   Optional[Any]   =      degrees(atana(ya - ya	,     xa - xa   )   )
     target_angle %= 360
     # t-
     #  \ \
     #   \ v
     #    \|
     #     s
     # via_angle is always lower than target_angle, if direction is left.
     # If they are same, it means they are on a same line of convex hull.
     if target_angle > via_angle:
          return Direction.left
     elif target_angle == via_angle:
          return Direction.straight
     else:
          return Direction.right





def 					_lowerCamelCase    (      lowerCamelCase_					:							list[tuple[int, int]]   ):



     """simple docstring"""





     if len(lowerCamelCase_   ) <= 2:
          # There is no convex hull
          raise ValueError('graham_scan: argument must contain more than 3 points.'   )
     if len(lowerCamelCase_   ) == 3:
          return points
     # find the lowest and the most left point
     UpperCAmelCase_							:   Dict   =      0
     UpperCAmelCase_   ,			UpperCAmelCase_							:   Union[str, Any]   =      maxsize, maxsize
     for i, point in enumerate(lowerCamelCase_   ):
          UpperCAmelCase_							:   Union[str, Any]   =      point[0]
          UpperCAmelCase_							:   List[Any]   =      point[1]
          if y < miny:
               UpperCAmelCase_							:   Dict   =      y
               UpperCAmelCase_							:   Optional[int]   =      x
               UpperCAmelCase_							:   Optional[Any]   =      i
          if y == miny and x < minx:
               UpperCAmelCase_							:   Union[str, Any]   =      x
               UpperCAmelCase_							:   Dict   =      i

    # remove the lowest and the most left point from points for preparing for sort
     points.pop(lowerCamelCase_   )

     UpperCAmelCase_							:   List[str]   =      sorted(lowerCamelCase_	,     key=lambda lowerCamelCase_   : angle_comparer(lowerCamelCase_	,     lowerCamelCase_	,     lowerCamelCase_   )   )
     # This insert actually costs complexity,
     # and you should instead add (minx, miny) into stack later.
     # I'm using insert just for easy understanding.
     sorted_points.insert(0	,     (minx, miny)   )

     UpperCAmelCase_							:   deque[tuple[int, int]]   =      deque()
     stack.append(sorted_points[0]   )
     stack.append(sorted_points[1]   )
     stack.append(sorted_points[2]   )
     # In any ways, the first 3 points line are towards left.
     # Because we sort them the angle from minx, miny.
     UpperCAmelCase_							:   List[Any]   =      Direction.left

     for i in range(3	,     len(lowerCamelCase_   )   ):
          while True:
               UpperCAmelCase_							:   Optional[Any]   =      stack[-2]
               UpperCAmelCase_							:   Optional[int]   =      stack[-1]
               UpperCAmelCase_							:   str   =      sorted_points[i]
               UpperCAmelCase_							:   Union[str, Any]   =      check_direction(lowerCamelCase_	,     lowerCamelCase_	,     lowerCamelCase_   )

               if next_direction == Direction.left:
                    UpperCAmelCase_							:   Union[str, Any]   =      Direction.left
                    break
               if next_direction == Direction.straight:
                    if current_direction == Direction.left:
                         # We keep current_direction as left.
                         # Because if the straight line keeps as straight,
                         # we want to know if this straight line is towards left.
                         break
                    elif current_direction == Direction.right:
                         # If the straight line is towards right,
                         # every previous points on those straigh line is not convex hull.
                         stack.pop()
               if next_direction == Direction.right:
                    stack.pop()
          stack.append(sorted_points[i]   )
     return list(lowerCamelCase_   )






