测试数据来自 system/2043

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　C国有个特殊的规定：一个人在一个城市最多只能赚 \(d(0 < d ≤ 1000)\) 元RMB，然后他必须到另一个城市工作。当然，他可以在别处工作一阵后又回来再赚 \(d\) 元RMB，然后又必须离开……。这样往往返返的次数没有限制。

　　城市间 \(m\) 条单向道路连接，共有 \(n\) 座城市（编号为1..n）。小H当前在城市 \(s\)。道路 \(i\) 从城市 \(a_i\) 到城市 \(b_i\)，在道路上行走不用花费任何费用。

　　为了帮助小H，他的父亲允许他使用他的私人飞机，飞机有 \(k\) 条航线，第 \(j\) 条航线是从城市 \(a_j\) 到城市 \(b_j\)，费用是 \(c_j(1≤c_j≤50000)\) 元RMB，如果小H手中没有现钱，可以用以后赚的钱来付机票钱，小H可以选择在任何时候，任何城市退休。

　　如果在工作时间上不作限制，小H总共可以赚多少钱呢？如果赚的钱不会出现上限，就输出 INF。

【输入格式】

　　第 1 行：五个用空格分开的整数 \(d,m,n,k,s\)。
　　第 2 到第 \(m+1\) 行：第 \(i+1\) 行包含 2 个空格分开的整数，表示从 \(a_i\) 到 \(b_i\) 的单向道路。
　　第 \(m+2\) 到 \(m+k+1\) 行：第 \(m+j\) 包括 3 个空格分开的整数，表示一条从 \(a_j\) 到 \(b_j\) 的单向航线，费用为 \(c_j\)。

【输出格式】

　　在上述规则下得最多可赚得钱数。

【输入输出样例1】

　Input

100 3 5 2 1
1 5
2 3
1 4
5 2 150
2 5 120

　Output

250

【输入输出样例2】

　Input

100 3 5 2 1
1 5
2 3
1 4
5 2 70
2 5 120

　Output

INF

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤300\)，\(1≤m≤150\)，\(1≤k≤350\)。

【来源】

　　Mr.he