[Usaco2009 Nov]找工作

奶牛们手头拮据，正在四处寻找工作。农夫约翰希望它们前往不同的城市碰碰运气，但有一项限制：一头奶牛每次在一座城市中最多只能赚取 $D$ 美元，之后必须前往另一座城市工作。它可以在其他城市工作一段时间后返回原来的城市，并再次赚取最多 $D$ 美元，往返次数不受限制。

共有 $C$ 座城市，编号为 $1$ 到 $C$ ，城市之间有 $P$ 条单向道路。第 $i$ 条道路从城市 $A_i$ 通往城市 $B_i$ ，通过道路不需要支付任何费用。贝希当前位于城市 $S$ 。

此外，农夫约翰还向贝希提供私人飞机服务。共有 $F$ 条单向航线，第 $i$ 条航线从城市 $J_i$ 飞往城市 $K_i$ ，费用为 $T_i$ 美元。即使贝希当前没有足够的现金，也可以先乘坐飞机，之后用工作所得支付费用。

贝希可以在任意时刻、任意城市退休。在工作时间不受限制的情况下，请计算贝希最多可以赚取多少钱。如果贝希可以赚取的钱没有上限，输出 $-1$ 。

输入格式

第一行包含 $5$ 个以空格分隔的整数 $D,P,C,F,S$ 。

接下来 $P$ 行，每行包含 $2$ 个以空格分隔的整数 $A_i,B_i$ ，表示一条从城市 $A_i$ 到城市 $B_i$ 的单向道路。

接下来 $F$ 行，每行包含 $3$ 个以空格分隔的整数 $J_i,K_i,T_i$ ，表示一条从城市 $J_i$ 到城市 $K_i$ 、费用为 $T_i$ 美元的单向航线。

输出一个整数，表示贝希最多可以赚取的钱数。如果可以赚取的钱没有上限，输出 $-1$ 。

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

贝希可以依次经过城市 $1$ 、 $5$ 、 $2$ 、 $3$ 。它在这 $4$ 座城市中共赚取 $4\times 100$ 美元，并支付从城市 $5$ 飞往城市 $2$ 的 $150$ 美元机票费用，因此最终赚取：

4\times 100-150=250

美元。

本题为 USACO 2009 November 试题「Job Hunt」，题面与测试数据整理自 BZOJ 2019。

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