output_description: If a+b=15, print `+`; if a\times b=15, print `*`; if neither holds, print `x`.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      a b
attempt: # ダイクストラ法
  # O(ElogV)
  import heapq
  
  
  def dijkstra_heap(s, edge):
      # 始点sから各頂点への最短距離
      d = [float("inf")] * (n + 1)
      used = [False] * (n + 1)
      d[s] = 0
      used[s] = True
      edgelist = []
      # edgelist : [sからの暫定(未確定)最短距離,頂点]のリスト
      # edge[s] : sから出る枝の[重み,終点]の配列
      for e in edge[s]:
          heapq.heappush(edgelist, e)  # sの隣の点は枝の重さがそのまま暫定最短距離となる
      while len(edgelist):
          # まだ使われてない頂点の中から最小の距離のものを探す→確定させる
          minedge = heapq.heappop(edgelist)
          # minedge : [sからの(確定)最短距離,頂点]
          v = minedge[1]
          if used[v]:
              continue
          d[v] = minedge[0]
          used[v] = True
          for e in edge[v]:
              if not used[e[1]]:
                  heapq.heappush(edgelist, [d[v] + e[0], e[1]])
      return d
  
  
  ################################
  n, m, s, t = map(int, input().split())  # n:頂点数　w:辺の数
  
  edge_yen = [[] for _ in range(n + 1)]
  edge_snuke = [[] for _ in range(n + 1)]
  
  for i in range(m):
      u, v, a, b = map(int, input().split())
      edge_yen[u].append([a, v])
      edge_yen[v].append([a, u])
      edge_snuke[u].append([b, v])
      edge_snuke[v].append([b, u])
  
  d_yen = dijkstra_heap(s, edge_yen)
  d_snuke = dijkstra_heap(t, edge_snuke)
  ans = [0] * (n)
  m = float("inf")
  for i in range(n, 0, -1):
      m = min(d_yen[i] + d_snuke[i], m)
      ans[i - 1] = 10**15 - m
  print(*ans, sep="\n")
  
problem_description: Statement
  
  You are given two integers a and b. Determine if a+b=15 or a\times b=15 or
  neither holds.
  
  Note that a+b=15 and a\times b=15 do not hold at the same time.
samples: [{"input": "4 11", "output": "+\n    \n\n4+11=15.\n\n* * *"}, {"input": "3 5", "output": "*\n    \n\n3\\times 5=15.\n\n* * *"}, {"input": "1 1", "output": "x\n    \n\n1+1=2 and 1\\times 1=1, neither of which is 15."}]