题目描述

在比特山,有一个风景胜地.它以纵横交错的滑雪轨道而出名. 而它们中的某些地区位于山顶或者很难到达的地方.因此人们使用滑雪电梯来帮助人们到达某些滑道.每个滑雪轨道和滑雪电梯的开始和结束都在一个空旷地带.而滑雪轨道都不会交叉,因此他们可以顺利的穿越. 而滑雪轨道和滑雪电梯都有一条或两条路线.

使用滑雪电梯必须要使用一种独特的磁卡,这个卡可以用现金购买.每个卡都含有一定数目的点数.使用滑雪电梯时必须付相应数目的点数.但留在卡上的点数并不能兑换成现金.

今天是比特风景区的最后一天.他的磁卡上还拥有一定数目的点数.他想尽最大可能的消费,以使得在离开比特山时,卡上剩余的点数最少. 你可以假定卡上的点数足以使他返回.

输入格式

第一行有两个整数$n$ 和 $n​'$, 他们之间用一个空格分开,他们分别表示空旷地带的数量和能直接返回的空旷地带数量(编号从$1$ 到 ​$n​'$ ).

在第二行有一个整整数$​k$​, 表示所有的滑雪轨道的数量. 接下来的$k$行,每行有由空格分开的两个整数. 分别表示开始和结束空旷地带编号.如果有上下两个轨道,则输出有两行(例如 p1 p2 和 p2 p1,并不一定按顺序).

在第$k+3$ 行有一个正整数​$m$​, 表示滑雪电梯的数量,接下来的m 行描述了每个滑雪电梯,每行有三个正整数$q_1,q_2$ 和 $r$; 分别表示起始和结束空旷地带编号和乘该电梯需要消费的点数. 如果有上下两部电梯,则表示为q1 q2 r1 和q2 q1 r2,并且上下的价格可能也不同.

最后一行为两个正整数 $b$ 和 $​s$​. $b$是当前他所处的空旷地带编号,s是他磁卡上的点数.

输出格式

第一行写入一个整数.为返回后卡上剩余的最少点数

样例

5 2
6
3 2
3 5
1 5
3 4
1 2
4 3
4
3 1 1
4 3 5
5 2 2
3 4 5
4 9

1

数据规模与约定

对于$100\%$的数据：

• $1\le n'<n\le 1000,1\le k\le 5000,1\le p_1<>p_2< n$,
• $1\le m\le 300,1 \le q_1 <> q_2 \le n​, 1 \le r \le 1000,1 \le b \le n​, 1 \le s \le 2000$.