U713441 赶路

出题：wzh 数据：ljm

小 C 正在从家赶往 zzsd 上课。 小 C 所在的 X 市共有 $n$ 个街区，$m$ 条双向道路。每条双向道路用 $(x_i,y_i,a_i,b_i)$ 表示这条双向道路连接了街区 $x_i$ 和 $y_i$，在**拥堵**时的通过时间为 $a_i$ 分钟，在**通畅**时的通过时间为 $b_i$ 分钟。 由于现在是早高峰，所以每条道路初始时都处于**拥堵**状态。而小 C 有神力，他可以选择至多 $k$ 条道路，并使其变成**通畅**状态。 小 C 的家在 $s$ 街区，zzsd 在 $t$ 街区，而小 C 只剩 $X$ 分钟上课了。也就是说，小 C 必须在 $X$ 分钟及以内到达 zzsd。而如果他迟到，那他将会被打断 $T-X$ 条腿，其中 $T$ 指他的用时。 现在小 C 想知道，他能否准时到达 zzsd？如果准时，能提前几分钟？不然要被打断几条腿？

第一行六个正整数 $n,m,s,t,k,X$。 接下来 $m$ 行，每行四个正整数 $x_i,y_i,a_i,b_i$ 描述一条双向道路。

格式如下： - 若小 C 能准时到达 zzsd，第一行输出一个字符串 $\texttt{safe}$，接下来一行一个正整数表示他最多能提前多久到达 zzsd。 - 否则，第一行输出一个字符串 $\texttt{my leg!!!}$，接下来输出一行一个正整数表示他最少要被打断几条腿。**若不可达，输出 $10^{18}$**。

对于所有数据，满足 $1 \le n,m \le 10^5,1 \le k \le 10,1 \le s,t,x_i,y_i \le n,1 \le X,a_i,b_i \le 10^9$。