问题描述

高桥君所居住的国家有 $N$ 个城镇，城镇之间通过 $M$ 条单向道路相连，每个城镇都被分配了从 $1$ 到 $N$ 的编号。第 $i$ 条道路可以从城镇 $a_i$ 移动到城镇 $b_i$，需要花费 $c_i$ 分钟。

持有零元的高桥君决定参加 $T$ 分钟的寻宝活动。高桥君在开始的时候（第 $0$ 分钟）位于编号为 $1$ 的城镇。而且，在从开始到第 $T$ 分钟的时间内，高桥君必须停留在编号为 $1$ 的城镇。如果高桥君在第 $i$ 个城镇停留了 $1$ 分钟，则他的所持金增加 $A_i$ 元。

请计算高桥君在 $T$ 分钟的寻宝活动中所能获得的最大金额。

输入

输入从标准输入中按以下格式给出。

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

• 第 $1$ 行有 $3$ 个整数 $N$、$M$ 和 $T$，分别表示城镇的数量、道路的数量和寻宝时间的分钟数$(2≦N≦10^5, 1≦M≦min(N(N-1),10^5), 1≦T≦10^9)$。这三个整数之间用空格分隔。
• 第 $2$ 行是一个包含 $N$ 个整数 $A_i(1≦A_i≦10^5)$ 的列表，表示在第 $i$ 个城镇停留时可获得的金钱。这 $N$ 个整数之间用空格分隔。
• 从第 $3$ 行开始的连续 $M$ 行中，每行包含 $3$ 个整数 $a_i, b_i, c_i (1≦a_i,b_i≦N,a_i≠b_i, 1≦c_i≦10^5)$，表示第 $i$ 条道路的信息。这 $M$ 行整数之间用空格分隔。
• 对于任意的 $i$ 和 $j$，当 $i\neq j$ 时，$a_i\neq a_j$ 或者 $b_i\neq b_j$。

输出

请输出高桥君在寻宝活动中可能获得的最大金额。输出占一行，不要忘记换行符。

部分分

本问题设有部分分。

• 当 $1≦N≦200$ 的数据满足要求时，可获得 $50$ 分。
• 完全正确且无其他约束的数据集可获得额外 $50$ 分，总分为 $100$ 分。

示例 1

2 2 5
1 3
1 2 2
2 1 1

输出示例 1

6

• 从开始到第 $0$ 分钟，需要 $2$ 分钟从城镇 $1$ 移动到城镇 $2$。
• 从开始到第 $2$ 分钟，停留 $2$ 分钟在城镇 $2$。此时所持金为 $6$ 元。
• 从开始到第 $4$ 分钟，需要 $1$ 分钟从城镇 $2$ 移动到城镇 $1$。
• 在第 $5$ 分钟，高桥君再次回到了城镇 $1$。寻宝活动结束。
• 这个案例满足部分分的限制条件。

示例 2

2 2 3
1 3
1 2 2
2 1 1

输出示例 2

3

• 在从开始到第 $T=3$ 分钟内，最佳选择是停留在城镇 $1$，可以将所持金增加到 $3$ 元。
• 这个案例满足部分分的限制条件。

示例 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

输出示例 3

1488

• 这个案例满足部分分的限制条件。