题目描述

小X非常无聊，打算去举世闻名、家喻户晓、赫赫有名、名扬四海、驰名中外、声名显赫的$n$号楼看看，但是小X很懒,他想要以最短的路程来到$n$号楼，小X为了更快的到达$n$号楼，开桂买了$k$把万能钥匙，$1$把万能钥匙能让全地图直接反转: 如果隐藏道路已经显现，把隐藏道路关闭，再把正常道路开启。 如果隐藏道路没有显现，则把隐藏道路开启，再把正常道路封闭。 隐藏道路和正常道路一共有m条，请问小X最少要走多少路程才能到达$n$号楼，如果不能到达，小X将会肥肠伤心，输出"xiaoXhenshangxin!!!"(没有"")

输入格式

第 $1$ 行包含$3$个正整数$n,m,k$，代表共有$n$栋楼，这 $n$ 栋楼之间有 $m$ 条道路，小X开桂买了 $k$ 把万能钥匙。接下来第 $2$ 到 $m+1$ 行，每行$4$个数 $u,v,w,p$ ,代表点 $u$ 和点 $v$ 之间有一条长度为 $w$ 的边，如果 $p$ 为 $1$ 则代表这条道路是正常道路,如果 $p$ 为 $0$ 则代表这条道路是隐藏道路。

输出格式

$1$ 号楼到 $n$ 号楼的最小距离。

5 12 3
1 2 4 1
1 3 3 1
2 3 5 1
2 4 6 1
4 5 10 1
1 4 22 1
1 2 3 0
1 3 5 0
4 5 5 0
2 4 10 0
2 5 99 0
3 5 20 0

14

提示

$1 \le n,k \le 1000$

$1 \le m \le 10000$

$1 \le w \le 10^{9}$

$1 \le u,v \le n$

$0 \le p \le 1$