output_description: Print the costs of SSSP in the following format.
  
      
      
      c0
      c1
      :
      c|V|-1
      
  
  The output consists of |V| lines. Print the cost of the shortest path from the
  source r to each vertex 0, 1, ... |V|-1 in order. If there is no path from the
  source to a vertex, print INF.
input_description: An edge-weighted graph G (V, E) and the source r.
  
      
      
      |V| |E| r
      s0 t0 d0
      s1 t1 d1
      :
      s|E|-1 t|E|-1 d|E|-1
      
  
  |V| is the number of vertices and |E| is the number of edges in G. The graph
  vertices are named with the numbers 0, 1,..., |V|-1 respectively. r is the
  source of the graph.
  
  si and ti represent source and target vertices of i-th edge (directed) and di
  represents the cost of the i-th edge.
attempt: inf = 1001001001
  nv, ne, r = map(int, input().split())
  d = [inf] * nv
  d[r] = 0
  e = []
  for i in range(ne):
      e.append(list(map(int, input().split())))
  for i in range(nv - 1):
      flg = False
      for j in e:
          if d[j[1]] > d[j[0]] + j[2]:
              flg = True
          d[j[1]] = min(d[j[1]], d[j[0]] + j[2])
      if not (flg):
          break
  for i in range(nv):
      print("INF" if d[i] == inf else d[i])
  
problem_description: Single Source Shortest Path
  
  For a given weighted graph G(V, E) and a source r, find the source shortest
  path to each vertex from the source (SSSP: Single Source Shortest Path).
samples: [{"input": "4 5 0\n    0 1 1\n    0 2 4\n    1 2 2\n    2 3 1\n    1 3 5", "output": "0\n    1\n    3\n    4"}, {"input": "4 6 1\n    0 1 1\n    0 2 4\n    2 0 1\n    1 2 2\n    3 1 1\n    3 2 5", "output": "3\n    0\n    2\n    INF"}]