407706: GYM102878 H Treasure Hunt

The double twelve is upcoming, and little LC has a lot of clothes, cosmetic and skincare products to buy. Since the double eleven just ended, LC is a little shy in her pocket, so she has to make money to satisfy her willingness to purchase.

LC finds a game called Treasure Hunt, a roguelike game, in which players can exchange game currency to real-life money. In this game, LC is given a directed acyclic graph(DAG) with $$$n$$$ nodes. LC can play as many turns as she wants. At the beginning of each turn, LC is at node $$$1$$$, she has to reach node $$$n$$$ to end this turn. When LC reaches node $$$i$$$, she will get $$$a_i$$$ gold coins as reward. However, every road $$$j$$$ has a pass limit $$$c_j$$$, which means if this road has been passed in $$$c_j$$$ turns, this road can no longer be used again.

LC wants to know the maximum gold coins she can earn from this game.

The first contains two integers $$$n\left(2\le n\le 100\right)$$$ and $$$m\left(1\le m\le 500\right)$$$, representing the number of nodes and the number of roads.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n\left(1\le a_i \le 100, i = 1, 2, \dots, n\right)$$$.

The next $$$m$$$ lines, each line contains 3 integers $$$u, v\left(1\le u, v\le n\right)$$$ and $$$c\left(1\le c\le 100\right)$$$.

Output one integer, the maximum gold coins LC can get.

4 4
1 4 3 2
1 2 1
1 3 1
2 4 1
3 4 1

13