该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

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

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

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

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

输入格式

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

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

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

输出格式

一个整数，表示阿龙最多能挣到的钱数。如果他可以挣到无穷多的钱，则输出 -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$