#381. 阿龙打工

阿龙打工

题目描述

CC 国有 NN 个大城市和 MM 条单向道路,每条道路连接这 NN 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 MM 条道路是免费通行的。

现在,政府部门又新修建了 KK 条单向道路。为了收回修路成本,新建的这 KK 条道路需要交通行费才可通行。

阿龙来到 CC 国打工。但是 CC 国为了保护当地居民的就业,出台了一项政策,限定来到任意一个城市的打工者在挣够 LL 元钱后必须离开。但是打工者离开后可以过一段时间再回来,这样他回来一次就可以在这个城市再挣 LL 元钱。而政策对于打工者离开后再返回的次数没有作出限定。

设 CC 国 NN 个城市的标号从 1∼N1\sim N,阿龙决定从 SS 号城市开始打工。开始时,他身无分文。好在他有一张无额度限制的信用卡,当需要交通行费时,如果他没有足够的钱,他可以先刷信用卡,待以后挣了钱再还上。

阿龙自然想挣尽可能多的钱。可是该如何规划自己的打工路线,才能挣到尽可能多的钱呢?

现在给出 NN个城市 M+KM+K 条道路的信息。请你告诉阿龙,他最多能挣到多少钱?如果他可以挣到无穷多的钱,则输出 -1

当然,最后计算挣到的钱时,应该先把信用卡支出的费用偿还上。

输入格式

第一行包含五个正整数 L,M,N,K,SL, M, N, K, S

接下来 MM 行,每行两个正整数 u,vu, v,表示从城市 uu 到城市 vv 有一条免费通行的单向道路。

接下来 KK 行,每行有 3 3 个正整数 x,y,zx,y,z,表示从城市 xx 到城市 yy 有一条通行费为 zz 的单向道路。

输出格式

一个整数,表示阿龙最多能挣到的钱数。如果他可以挣到无穷多的钱,则输出 -1

样例输入1

200 3 5 2 1
1 2
1 3
4 5
2 4 300
4 2 200

样例输出1

500

样例输入2

200 3 5 2 1
1 2
1 3
4 5
2 4 100
4 2 200

样例输出2

-1

【数据范围】

对于 100%的数据,$1 ≤ L ≤ 1,000; 1 ≤ M ≤ 150; 2 ≤ N ≤ 250; 1 ≤ S, u, v, x, y ≤ N; 1 <= K <= 350; 1 ≤ z <= 5×10^4$