魔法祝福

题目背景

$ A $到了宝塔的大门前,据说塔第$ q $层藏了一个惊天的宝藏——dalao的~~祝福~~>>(zu zhou),让你NOIP2018 ~~AK~~>>(bao 0)全场。但以你的智商O__O “…

题目描述

宝塔有$ n $层,A向一个dalao购买了魔法,可以从第$ x $层跳到第$ y $层,也可以从第$ y $层跳到$ x $层。但每种魔法都有诅咒和一个分值$ k $,每使用一次魔法,会用$ t $个单位的时间,也就会得到一个诅咒,如果你的诅咒数大于等于这个魔法的分值$ k $,那么这个魔法就不能使用了(在这之前魔法无限使用)。$ A $的初始诅咒值为-1。 $ A $被dalao强制使用了一次魔法($ A $本身不会这个魔法),从第一层跳到了第$ p $层($ p $可以是1)。望眼四周,空空如也,没有路。要到达遥远的第$ q $层,好像只能编程了吧。输出最少到达所需的时间。如果到天荒地老都到不了,输出“bao 0”(不包含单引号)。

输入输出格式

输入格式


第1行,输入4个整数$ n $ ,$ m $,$ p $,$ q $(保证$ p $≠$ q $) 第2行到第$ m $+1行,输入4个整数$ x $,$ y $,$ t $,$ k $。

输出格式


输出仅一行,输出最小时间或“bao 0”。

输入输出样例

输入样例 #1

5 6 1 5
1 2 5 2
1 3 1 3
2 4 3 2
5 4 1 1
5 3 2 2
3 4 7 5

输出样例 #1

3

说明

对于 $ 20\% $ 的数据,$ 1 \leq n,p,q \leq 4*10^2,m,k \leq 10^3,t \leq 3*10^2 $; 对于 $ 50\% $ 的数据,$ 1 \leq n,p,q \leq 5*10^3,m,k \leq 10^5,t \leq 10^6 $; 对于 $ 100\% $ 的数据,$ 1 \leq n,p,q \leq 10^6,m,k \leq 10^6,t \leq 10^8 $。