题目背景

$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”。

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

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$。