

'''simple docstring'''






import unittest
from dataclasses import dataclass
from typing import Optional

from transformers.utils import ModelOutput
@dataclass
class      SCREAMING_SNAKE_CASE__      (    _UpperCAmelCase				):
    _A         =							42
    _A         =							None
    _A         =							None






class      SCREAMING_SNAKE_CASE__      (    unittest.TestCase				):




    def   __lowerCamelCase				( self      ):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_				:      int					=	ModelOutputTest(a=30      )
          self.assertEqual(x.a    ,					30      )
          self.assertIsNone(x.b      )
          self.assertIsNone(x.c      )
          with self.assertRaises(lowercase__      ):
                SCREAMING_SNAKE_CASE_				:      str					=	x.d




    def   __lowerCamelCase				( self      ):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_				:      List[str]					=	ModelOutputTest(a=30    ,					b=10      )
          self.assertEqual(x[0]    ,					30      )
          self.assertEqual(x[1]    ,					10      )
          self.assertEqual(x[:2]    ,					(30, 10)      )
          self.assertEqual(x[:]    ,					(30, 10)      )

          SCREAMING_SNAKE_CASE_				:      Tuple					=	ModelOutputTest(a=30    ,					c=10      )
          self.assertEqual(x[0]    ,					30      )
          self.assertEqual(x[1]    ,					10      )
          self.assertEqual(x[:2]    ,					(30, 10)      )
          self.assertEqual(x[:]    ,					(30, 10)      )




    def   __lowerCamelCase				( self      ):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_				:      List[Any]					=	ModelOutputTest(a=30    ,					b=10      )
          self.assertEqual(x["a"]    ,					30      )
          self.assertEqual(x["b"]    ,					10      )
          with self.assertRaises(lowercase__      ):
                SCREAMING_SNAKE_CASE_				:      Union[str, Any]					=	x["c"]

          SCREAMING_SNAKE_CASE_				:      List[str]					=	ModelOutputTest(a=30    ,					c=10      )
          self.assertEqual(x["a"]    ,					30      )
          self.assertEqual(x["c"]    ,					10      )
          with self.assertRaises(lowercase__      ):
                SCREAMING_SNAKE_CASE_				:      int					=	x["b"]




    def   __lowerCamelCase				( self      ):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_				:      List[Any]					=	ModelOutputTest(a=30      )
          self.assertEqual(list(x.keys()      )    ,					["a"]      )
          self.assertEqual(list(x.values()      )    ,					[30]      )
          self.assertEqual(list(x.items()      )    ,					[("a", 30)]      )
          self.assertEqual(list(lowercase__      )    ,					["a"]      )

          SCREAMING_SNAKE_CASE_				:      List[Any]					=	ModelOutputTest(a=30    ,					b=10      )
          self.assertEqual(list(x.keys()      )    ,					["a", "b"]      )
          self.assertEqual(list(x.values()      )    ,					[30, 10]      )
          self.assertEqual(list(x.items()      )    ,					[("a", 30), ("b", 10)]      )
          self.assertEqual(list(lowercase__      )    ,					["a", "b"]      )

          SCREAMING_SNAKE_CASE_				:      List[str]					=	ModelOutputTest(a=30    ,					c=10      )
          self.assertEqual(list(x.keys()      )    ,					["a", "c"]      )
          self.assertEqual(list(x.values()      )    ,					[30, 10]      )
          self.assertEqual(list(x.items()      )    ,					[("a", 30), ("c", 10)]      )
          self.assertEqual(list(lowercase__      )    ,					["a", "c"]      )

          with self.assertRaises(lowercase__      ):
                SCREAMING_SNAKE_CASE_				:      str					=	x.update({"d": 20}      )
          with self.assertRaises(lowercase__      ):
                del x["a"]
          with self.assertRaises(lowercase__      ):
                SCREAMING_SNAKE_CASE_				:      Optional[int]					=	x.pop("a"      )
          with self.assertRaises(lowercase__      ):
                SCREAMING_SNAKE_CASE_				:      List[Any]					=	x.setdefault("d"    ,					32      )




    def   __lowerCamelCase				( self      ):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_				:      Optional[int]					=	ModelOutputTest(a=30      )
          SCREAMING_SNAKE_CASE_				:      int					=	10
          self.assertEqual(x.a    ,					10      )
          self.assertEqual(x["a"]    ,					10      )




    def   __lowerCamelCase				( self      ):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_				:      Tuple					=	ModelOutputTest(a=30      )
          SCREAMING_SNAKE_CASE_				:      Dict					=	10
          self.assertEqual(x.a    ,					10      )
          self.assertEqual(x["a"]    ,					10      )




    def   __lowerCamelCase				( self      ):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_				:      Optional[Any]					=	ModelOutputTest({"a": 30, "b": 10}      )
          self.assertEqual(list(x.keys()      )    ,					["a", "b"]      )
          self.assertEqual(x.a    ,					30      )
          self.assertEqual(x.b    ,					10      )







    def   __lowerCamelCase				( self      ):






          """simple docstring"""






          SCREAMING_SNAKE_CASE_				:      Tuple					=	ModelOutputTest([("a", 30), ("b", 10)]      )
          self.assertEqual(list(x.keys()      )    ,					["a", "b"]      )
          self.assertEqual(x.a    ,					30      )
          self.assertEqual(x.b    ,					10      )

          with self.assertRaises(lowercase__      ):
                SCREAMING_SNAKE_CASE_				:      Union[str, Any]					=	ModelOutputTest([("a", 30), (10, 10)]      )

          SCREAMING_SNAKE_CASE_				:      List[str]					=	ModelOutputTest(a=(30, 30)      )
          self.assertEqual(list(x.keys()      )    ,					["a"]      )
          self.assertEqual(x.a    ,					(30, 30)      )




'''simple docstring'''






import heapq


def  __lowerCamelCase      (				SCREAMING_SNAKE_CASE_					:     List[str]  ,  SCREAMING_SNAKE_CASE_					:     Any  ,  SCREAMING_SNAKE_CASE_					:     Tuple   )							->       Union[str, Any]:
      """simple docstring"""

      SCREAMING_SNAKE_CASE_				:      Optional[int]					=	[(0, start)]  # cost from start node,end node
      SCREAMING_SNAKE_CASE_				:      str					=	set()
      while heap:
            ((SCREAMING_SNAKE_CASE_),						(SCREAMING_SNAKE_CASE_))				:      Optional[int]					=	heapq.heappop(SCREAMING_SNAKE_CASE_   )
            if u in visited:
                  continue
            visited.add(SCREAMING_SNAKE_CASE_   )
            if u == end:
                  return cost
            for v, c in graph[u]:
                  if v in visited:
                        continue
                  SCREAMING_SNAKE_CASE_				:      int					=	cost + c
                  heapq.heappush(SCREAMING_SNAKE_CASE_  ,  (next_item, v)   )
      return -1


snake_case_					  =	{
    'A': [['B', 2], ['C', 5]],
    'B': [['A', 2], ['D', 3], ['E', 1], ['F', 1]],
    'C': [['A', 5], ['F', 3]],
    'D': [['B', 3]],
    'E': [['B', 4], ['F', 3]],
    'F': [['C', 3], ['E', 3]],
}
snake_case_					  =	{
    'B': [['C', 1]],
    'C': [['D', 1]],
    'D': [['F', 1]],
    'E': [['B', 1], ['F', 3]],
    'F': [],
}
snake_case_					  =	{
    'B': [['C', 1]],
    'C': [['D', 1]],
    'D': [['F', 1]],
    'E': [['B', 1], ['G', 2]],
    'F': [],
    'G': [['F', 1]],
}

snake_case_					  =	dijkstra(G, 'E', 'C')
print(short_distance)  # E -- 3 --> F -- 3 --> C == 6

snake_case_					  =	dijkstra(Ga, 'E', 'F')
print(short_distance)  # E -- 3 --> F == 3

snake_case_					  =	dijkstra(Ga, 'E', 'F')
print(short_distance)  # E -- 2 --> G -- 1 --> F == 3

if __name__ == "__main__":
      import doctest

      doctest.testmod()

