题目描述

小A虽然拥有身为摸鱼人的高贵属性，但还是不幸被老板选中派出去出差，值得庆幸的是公司给予小A出差的财务经费是 $x$ 元。在去出差地的所有方式中，小A最终选择的是工带航空，工带航空历史悠久，名誉拉满，从公司成立至今从来没有发生过一次事故，是每一个需要坐经常坐飞机的人最值得信赖的伙伴，最重要的是，这个航空公司有他的最好的死党，可以给定他一定的优惠。

当他把这件事告诉他的死党时，他的死党跟他说：“ 作为你最好的朋友，我可以提前给你 $m$ 条非免费航班的路线提前帮他订上票，以免抢不上票，以及 $k$ 条免费航班，但 $k$ 条里面你只能选一条，如果选多了我就会被老板炒鱿鱼了。” 小A很高兴，但他发现如果妥善规划死党给的路线可以转机从而可能花更少的钱，于是他想让你帮他算一下，他是否会走免费路线，并且免费路线是哪条，以及最少会花多少钱，剩下的钱他打算买著名恋爱养成类游戏——老头环。

输入格式

第$1$行输入 $n , m , k , s , e , x ,$ $n$ ($1~\\le~n~\\le~5\\cdot 10^5$)为城市数量 , $m$ ($1~\\le~m~\\le~5\\cdot 10^5$)为非免费航班数量，$k$ ($1~\\le~k~\\le~5\\cdot 10^5$)为免费航班数量，$s$ ($1~\\le~s~\\le~n$)为起点，$e$ ($1~\\le~e~\\le~n$)为终点, $x$ ($1~\\le~x~\\le~10^{18}$)为公司给小A的财务经费。

第$2$行至第$1+m$行，每行分别为$a,b,c$ ( $1~\\le~a~\\le~n~,~1~\\le~b~\\le~n~,~1~\\le~c~\\le~n $ ) , $a$ 和 $b$ 为航线两端城市，$c$ 为该航班所需花费（从$a$能飞向$b$，从$b$也能飞向$a$）

第$2+m$行至$1+m+k$行，每行为 $a , b$ ($1~\\le~a~\\le n~,~1~\\le~b~\\le~n$) , $a$ 和 $b$ 为航线两端城市，该航线免费（从$a$能飞向$b$，从$b$也能飞向$a$）

输出格式

第一行输出 Yes 或 No，代表是否会走免费路线

第二行输出 $a$ 和 $b$ ，$a$ 和 $b$ 为免费航线两端城市，如果未使用免费路线则输出 $-1 -1$（ $a$ 和 $b$ 的输出顺序与读入时顺序相同）

第三行输出 Yes 或 No，代表公司给小A的经费能否将花费全部报销

第四行输出 $z$ , $z$ 为小A还能剩下多少钱（如果无法全部报销则输出 $-1$，因为小A不想花自己的钱，摆烂辞职不去了 ）

tips: cin,cout有可能超时，谨慎使用。

样例

4 3 1 1 4 1 
1 2 1 
1 3 2 
2 4 3 
3 4

No 
-1 -1 
No 
-1

7 5 2 1 7 8 
1 4 1 
1 5 2 
1 7 10 
4 7 8 
5 7 5 
2 4 
6 7

No 
-1 -1 
Yes 
1

提示

1.如果无法全部报销则自动认为不会走免费路线.

2.如果使用免费线路剩下的钱和不使用免费路线剩下的钱一样，则不使用免费路线(避免浪费人情).