output_description: Print the minimum number of strokes Snuke takes to travel from the square
  (x_1,y_1) to (x_2,y_2), or print `-1` if the travel is impossible.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      H W K
      x_1 y_1 x_2 y_2
      c_{1,1}c_{1,2} .. c_{1,W}
      c_{2,1}c_{2,2} .. c_{2,W}
      :
      c_{H,1}c_{H,2} .. c_{H,W}
attempt: import sys
  
  
  def main(lines):
      n, m, s = map(int, lines[0].split())
      adj = [[] for _ in range(n)]
      for i in range(m):
          a, b, d = map(int, lines[i + 1].split())
          adj[a].append((b, d))
      from heapq import heappush, heappop
  
      inf = 10**9
      node = []
      dist = [inf] * n
      done = [False] * n
      dist[s] = 0
      heappush(node, (0, s))
      while node:
          cost, v = heappop(node)
          if not done[v]:
              for e in adj[v]:
                  if dist[e[0]] > dist[v] + e[1]:
                      dist[e[0]] = dist[v] + e[1]
                      heappush(node, (dist[e[0]], e[0]))
          done[v] = True
      for el in dist:
          if el == inf:
              print("INF")
          else:
              print(el)
  
  
  if __name__ == "__main__":
      lines = []
      for l in sys.stdin:
          lines.append(l.rstrip("\r\n"))
      main(lines)
  
problem_description: Statement
  
  Snuke, a water strider, lives in a rectangular pond that can be seen as a grid
  with H east-west rows and W north-south columns. Let (i,j) be the square at
  the i-th row from the north and j-th column from the west.
  
  Some of the squares have a lotus leaf on it and cannot be entered. The square
  (i,j) has a lotus leaf on it if c_{ij} is `@`, and it does not if c_{ij} is
  `.`.
  
  In one stroke, Snuke can move between 1 and K squares (inclusive) toward one
  of the four directions: north, east, south, and west. The move may not pass
  through a square with a lotus leaf. Moving to such a square or out of the pond
  is also forbidden.
  
  Find the minimum number of strokes Snuke takes to travel from the square
  (x_1,y_1) to (x_2,y_2). If the travel from (x_1,y_1) to (x_2,y_2) is
  impossible, point out that fact.
samples: [{"input": "3 5 2\n    3 2 3 4\n    .....\n    .@..@\n    ..@..", "output": "5\n    \n\nInitially, Snuke is at the square (3,2). He can reach the square (3, 4) by\nmaking five strokes as follows:\n\n  * From (3, 2), go west one square to (3, 1).\n\n  * From (3, 1), go north two squares to (1, 1).\n\n  * From (1, 1), go east two squares to (1, 3).\n\n  * From (1, 3), go east one square to (1, 4).\n\n  * From (1, 4), go south two squares to (3, 4).\n\n* * *"}, {"input": "1 6 4\n    1 1 1 6\n    ......", "output": "2\n    \n\n* * *"}, {"input": "3 3 1\n    2 1 2 3\n    .@.\n    .@.\n    .@.", "output": "-1"}]