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: import sys
  from heapq import heappush, heappop
  
  inf = 1 << 30
  
  
  def solve():
      N, M, s = map(int, sys.stdin.readline().split())
      Adj = [[] for i in range(N)]
  
      for i in range(M):
          ui, vi, ci = map(int, sys.stdin.readline().split())
          Adj[ui].append((vi, ci))
  
      d = dijkstra(N, Adj, s)
  
      for di in d:
          print(di if di < inf else "INF")
  
  
  def dijkstra(N, Adj, s):
      d = [inf] * N
      p = [-1] * N
      fixed = [False] * N
      d[s] = 0
      p[s] = s
      pq = [(0, s)]
  
      for i in range(N - 1):
          while pq:
              di, v = heappop(pq)
  
              if not fixed[v] and di == d[v]:
                  break
  
          fixed[v] = True
  
          for u, c in Adj[v]:
              if d[v] + c < d[u]:
                  d[u] = d[v] + c
                  p[u] = v
                  heappush(pq, (d[u], u))
  
      return d
  
  
  if __name__ == "__main__":
      solve()
  
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"}]