Problem Description

In the country where Takahashi lives, there are $ N $ towns connected by one-way roads, and each town is numbered from $ 1 $ to $ N $. The $ i $-th road allows movement from town $ a_i $ to town $ b_i $ and takes $ c_i $ minutes to travel.

Takahashi, starting with $ 0 $ yen, decided to go on a treasure hunt for $ T $ minutes. At the start of $ 0 $ minutes, Takahashi is in town $ 1 $. He must also be in town $ 1 $ at the $ T $-minute mark. Staying in town $ i $ for $ 1 $ minute adds $ A_i $ yen to Takahashi's money.

Determine the maximum amount of money Takahashi can have after $ T $ minutes of treasure hunting.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ T $ $ A_1 $ … $ A_N $ $ a_1 $ $ b_1 $ $ c_1 $ . . . $ a_M $ $ b_M $ $ c_M $

• The first line contains three integers $N, M, T\ (2≦N≦10^5,\ 1≦M≦min(N(N-1),10^5),\ 1≦T≦10^9)$ representing the number of towns, the number of roads, and the duration of the treasure hunt, separated by spaces.
• The second line contains integers $ A_i(1≦A_i≦10^5) $ separated by spaces, representing the money gained by staying in town $ i $.
• The following $ M $ lines contain three integers $a_i, b_i, c_i\ (1≦a_i,b_i≦N, a_i≠b_i,\ 1≦c_i≦10^5)$ separated by spaces, representing the information of the $ i $-th road.
• For any $ i≠j $, either $ a_i≠a_j $ or $ b_i≠b_j $ holds.

Output Format

Output the maximum amount of money Takahashi can have after the treasure hunt in one line. Do not forget to add a newline.

Sample Input and Output

Sample Input #1

2 2 5
1 3
1 2 2
2 1 1

Sample Output #1

6

Sample Input #2

2 2 3
1 3
1 2 2
2 1 1

Sample Output #2

3

Sample Input #3

8 15 120
1 2 6 16 1 3 11 9
1 8 1
7 3 14
8 2 13
3 5 4
5 7 5
6 4 1
6 8 17
7 8 5
1 4 2
4 7 1
6 1 3
3 1 10
2 6 5
2 4 12
5 1 30

Sample Output #3

1488

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset satisfying $ 1≦N≦200 $, you will be awarded $ 50 $ points.
• If you solve the dataset without additional constraints, you will be awarded an additional $ 50 $ points, totaling $ 100 $ points.

Sample Explanation 1

• Move from town $ 1 $ to town $ 2 $ in $ 2 $ minutes from the start.
• Stay in town $ 2 $ for $ 2 $ minutes from the $ 2 $-minute mark. The money becomes $ 6 $ yen.
• Move from town $ 2 $ to town $ 1 $ in $ 1 $ minute from the $ 4 $-minute mark.
• Be in town $ 1 $ at the $ 5 $-minute mark. The treasure hunt ends.
• This case satisfies the partial points constraint.

Sample Explanation 2

• Staying in town $ 1 $ for $ 3 $ minutes from the start is optimal, making the money $ 3 $ yen.
• This case satisfies the partial points constraint.

Sample Explanation 3

• This case satisfies the partial points constraint.

见题面 Input 部分

见题面 Output 部分