题目描述
布布是一只喜欢探险的猴子。有一次,她在森林里迷路了(不仅仅是去探险,还要去找香蕉和桃子),森林里的每个地方都有一个编号1~n。幸好她所在的森林有路标,这些路标会告诉她从她所在的地方可以到达哪里,以及到达另一个地方的时间。布布所在的地方为s地,他想去k地玩,这个森林的出口是t地。但是布布找了一天的香蕉和桃子,很累了,更重要的是她也很饿……她必须在m时间内到达k地再出森林。所有的路标的起点终点值均包含上文的s,k和t。
输入格式
第一行是n,s,t,k,m,其中n≤1000;
第二行是bian,代表边的数目,bian≤200000;
接下来bian行,每行3个数,分别为ui,vi,ri,表示从ui地到vi地需要ri个单位时间。(ri≤maxlongint)
注意:
1. 从a 到b的路径 不意味着b也可以到a ;
2. 必须先到k 才能到t ;
3. 所有数据均为正整数,且答案小于maxlongint。
输出格式
如果布布可以在规定时间内走出森林,则第一行输出‘Yes’,否则输出‘No’;第二行输出布布走出森林的最少时间。
样例输入
样例输出