問題文
在高桥君居住的国家, N 每个城镇都有单向道路连接。 M 每个城镇都有书。 编号 1 它们的编号最大为 N 已分配。 i 路径是 a_i 从班镇出发 b_i 可以搬到城镇 需要 c_i 分钟。
手里有钱 0 高桥日元是 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 在线 一个整数,表示住在 i 城镇时赚取的金额。 接行 A_i(1≦A_i≦10^5) 用空格分隔。
- 3 在行 M 行数过多 关于第 i 中, i 代表路径的信息 3 整数 a_i, b_i, c_i (1≦a_i,b_i≦N,a_i≠b_i, 1≦c_i≦10^5)用空格分隔。
- i≠j 在 i,j 中,a_i≠a_j 或 如果 b_i≠b_j 任一成立。
出力
高桥寻宝所获得的最大金钱。 在 1 行输出。不要忘记换行符。
部分点
针对此问题设置了部分分数。
- 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
- 開始 0 分钟开始 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
- 这种情况满足部分点约束。 最好留在