'''simple docstring'''


from collections import deque


def    _lowerCamelCase       ( lowerCamelCase_   :				List[str]  ):



     """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_				:  Union[str, Any]  = []

     for e in range(lowerCamelCase_  ):
          UpperCAmelCase_  ,     UpperCAmelCase_				:  Optional[Any]  = (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_				:  List[Any]  = []

     for e in range(lowerCamelCase_  ):
          UpperCAmelCase_  ,     UpperCAmelCase_				:  Any  = (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_				:  int  = []

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

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

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


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



     """simple docstring"""





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


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



     """simple docstring"""





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


def    _lowerCamelCase       ( lowerCamelCase_   :				Optional[int]      ,	lowerCamelCase_   :				Any  ):



     """simple docstring"""





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


def    _lowerCamelCase       ( lowerCamelCase_   :				Optional[Any]      ,	lowerCamelCase_   :				List[Any]=None      ,	lowerCamelCase_   :				Tuple=None  ):



     """simple docstring"""





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


def    _lowerCamelCase       ( lowerCamelCase_   :				str  ):



     """simple docstring"""





     ((UpperCAmelCase_)  ,     (UpperCAmelCase_))				:  str  = a_and_n
     UpperCAmelCase_				:  List[str]  = list(lowerCamelCase_  )
     UpperCAmelCase_				:  Any  = [[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_				:  str  = dist[i][k] + dist[k][j]
                         UpperCAmelCase_				:  Union[str, Any]  = k
     print(lowerCamelCase_  )


def    _lowerCamelCase       ( lowerCamelCase_   :				Dict      ,	lowerCamelCase_   :				Tuple  ):



     """simple docstring"""





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


def    _lowerCamelCase       ( ):



     """simple docstring"""





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


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



     """simple docstring"""





     ((UpperCAmelCase_)  ,     (UpperCAmelCase_))				:  Optional[Any]  = e_and_n
     e.sort(reverse=lowerCamelCase_      ,	key=lambda lowerCamelCase_  : x[2]  )
     UpperCAmelCase_				:  str  = [{i} for i in range(1      ,	n + 1  )]
     while True:
          if len(lowerCamelCase_  ) == 1:
               break
          print(lowerCamelCase_  )
          UpperCAmelCase_				:  List[str]  = 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_   :				Tuple  ):



     """simple docstring"""





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







'''simple docstring'''


import sys
from dataclasses import dataclass
from typing import TYPE_CHECKING, Dict, List, Optional, Tuple, Union

import pandas as pd
import pyarrow as pa

import datasets
import datasets.config
from datasets.features.features import require_storage_cast
from datasets.table import table_cast


if TYPE_CHECKING:
 import sqlitea

 import sqlalchemy


snake_case__	:     int      =    datasets.utils.logging.get_logger(__name__)






@dataclass
class 	__SCREAMING_SNAKE_CASE		(			datasets.BuilderConfig			):







  '''simple docstring'''






  lowerCamelCase_						:Union[str, "sqlalchemy.sql.Selectable"]		       =						None
  lowerCamelCase_						:Union[str, "sqlalchemy.engine.Connection", "sqlalchemy.engine.Engine", "sqlite3.Connection"]		       =						None
  lowerCamelCase_						:Optional[Union[str, List[str]]]		       =						None
  lowerCamelCase_						:bool		       =						True
  lowerCamelCase_						:Optional[Union[List, Tuple, Dict]]		       =						None
  lowerCamelCase_						:Optional[Union[List, Dict]]		       =						None
  lowerCamelCase_						:Optional[List[str]]		       =						None
  lowerCamelCase_						:Optional[int]		       =						1_0000
  lowerCamelCase_						:Optional[datasets.Features]		       =						None


  def _UpperCamelCase	(					self		):




       '''simple docstring'''

       if self.sql is None:
            raise ValueError('sql must be specified'		)
       if self.con is None:
            raise ValueError('con must be specified'		)


  def _UpperCamelCase	(					self ,						snake_case_ ,						snake_case_ = None ,						):




       '''simple docstring'''

       UpperCAmelCase_				:  List[Any]  = config_kwargs.copy()
       # We need to stringify the Selectable object to make its hash deterministic

       # The process of stringifying is explained here: http://docs.sqlalchemy.org/en/latest/faq/sqlexpressions.html
       UpperCAmelCase_				:  str  = config_kwargs['sql']
       if not isinstance(snake_case_ ,						snake_case_		):
            if datasets.config.SQLALCHEMY_AVAILABLE and "sqlalchemy" in sys.modules:
                 import sqlalchemy

                 if isinstance(snake_case_ ,						sqlalchemy.sql.Selectable		):
                      UpperCAmelCase_				:  Any  = sqlalchemy.create_engine(config_kwargs['con'].split('://'		)[0] + '://'		)
                      UpperCAmelCase_				:  int  = str(sql.compile(dialect=engine.dialect		)		)
                      UpperCAmelCase_				:  str  = sql_str
                 else:
                      raise TypeError(
                          F'''Supported types for \'sql\' are string and sqlalchemy.sql.Selectable but got {type(snake_case_		)}: {sql}'''		)
            else:
                 raise TypeError(
                     F'''Supported types for \'sql\' are string and sqlalchemy.sql.Selectable but got {type(snake_case_		)}: {sql}'''		)
       UpperCAmelCase_				:  Union[str, Any]  = config_kwargs['con']
       if not isinstance(snake_case_ ,						snake_case_		):
            UpperCAmelCase_				:  Optional[Any]  = id(snake_case_		)
            logger.info(
                F'''SQL connection \'con\' of type {type(snake_case_		)} couldn\'t be hashed properly. To enable hashing, specify \'con\' as URI string instead.'''		)

       return super().create_config_id(snake_case_ ,						custom_features=snake_case_		)






  @property
  def _UpperCamelCase	(					self		):




       '''simple docstring'''

       UpperCAmelCase_				:  List[Any]  = {
           'index_col': self.index_col,
           'columns': self.columns,
           'params': self.params,
           'coerce_float': self.coerce_float,
           'parse_dates': self.parse_dates,
       }
       return pd_read_sql_kwargs







class 	__SCREAMING_SNAKE_CASE		(			datasets.ArrowBasedBuilder			):







  '''simple docstring'''






  lowerCamelCase_						:Any		       =						SqlConfig


  def _UpperCamelCase	(					self		):




       '''simple docstring'''

       return datasets.DatasetInfo(features=self.config.features		)


  def _UpperCamelCase	(					self ,						snake_case_		):




       '''simple docstring'''

       return [datasets.SplitGenerator(name=datasets.Split.TRAIN ,						gen_kwargs={}		)]


  def _UpperCamelCase	(					self ,						snake_case_		):




       '''simple docstring'''

       if self.config.features is not None:
            UpperCAmelCase_				:  Tuple  = self.config.features.arrow_schema
            if all(not require_storage_cast(snake_case_		) for feature in self.config.features.values()		):
                 # cheaper cast
                 UpperCAmelCase_				:  Tuple  = pa.Table.from_arrays([pa_table[field.name] for field in schema] ,						schema=snake_case_		)
            else:
                 # more expensive cast; allows str <-> int/float or str to Audio for example
                 UpperCAmelCase_				:  Union[str, Any]  = table_cast(snake_case_ ,						snake_case_		)
       return pa_table






  def _UpperCamelCase	(					self		):




       '''simple docstring'''

       UpperCAmelCase_				:  Optional[Any]  = self.config.chunksize
       UpperCAmelCase_				:  Optional[Any]  = pd.read_sql(
           self.config.sql ,						self.config.con ,						chunksize=snake_case_ ,						**self.config.pd_read_sql_kwargs		)
       UpperCAmelCase_				:  int  = [sql_reader] if chunksize is None else sql_reader
       for chunk_idx, df in enumerate(snake_case_		):
            UpperCAmelCase_				:  Optional[Any]  = pa.Table.from_pandas(snake_case_		)
            yield chunk_idx, self._cast_table(snake_case_		)






