output_description: Print the answer.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      D_1 D_2 ... D_N
attempt: import heapq
  
  
  class Dijkstra:
  
      def __init__(self, rote_map, start_point, goal_point=None):
          self.rote_map = rote_map
          self.start_point = start_point
          self.goal_point = goal_point
  
      def execute(self):
          num_of_city = len(self.rote_map)
          dist = [10**16 for _ in range(num_of_city)]
          prev = [10**16 for _ in range(num_of_city)]
  
          dist[self.start_point] = 0
          heap_q = []
          heapq.heappush(heap_q, (0, self.start_point))
          while len(heap_q) != 0:
              prev_cost, src = heapq.heappop(heap_q)
              if dist[src] < prev_cost:
                  continue
              if src == self.goal_point:
                  return prev_cost
  
              for dest, cost in self.rote_map[src].items():
                  if dist[dest] > prev_cost + cost:
                      dist[dest] = prev_cost + cost
                      heapq.heappush(heap_q, (dist[dest], dest))
                      prev[dest] = src
          return -1
  
  
  n, m = map(int, input().split())
  route_map = [dict() for _ in range(n)]
  
  for i in range(m):
      u, v, a = map(int, input().split())
      u, v = u - 1, v - 1
      route_map[u][v] = a
  
  for i in range(n - 1):
      u, v = i + 1, i
      route_map[u][v] = 0
  
  
  # ゴールまでの最短経路
  print(Dijkstra(route_map, 0, n - 1).execute())
  
problem_description: Statement
  
  Given is an integer sequence D_1,...,D_N of N elements. Find the number,
  modulo 998244353, of trees with N vertices numbered 1 to N that satisfy the
  following condition:
  
    * For every integer i from 1 to N, the distance between Vertex 1 and Vertex i is D_i.
samples: [{"input": "4\n    0 1 1 2", "output": "2\n    \n\nFor example, a tree with edges (1,2), (1,3), and (2,4) satisfies the\ncondition.\n\n* * *"}, {"input": "4\n    1 1 1 1", "output": "0\n    \n\n* * *"}, {"input": "7\n    0 3 2 1 2 2 1", "output": "24"}]