Road

$\ \ \ \ $Windy August like to fly in the sky ,together with the wind.But she will feel very tired after a long-time-flying,so she usually choose to walk.

$\ \ \ \ $Now there are $n$ sights,and there are $m$ roads between some of the sights.The roads are described in the format like $(a,b,c,d,w)$,saying that there are roads between every nodes $(x,y)$ ,$a\le x\le b$,$c\le y\le d$,and the cost of the roads are w.Windy August will start off at the nodes numbered 1,and she will go to the node numbered n.She can fly $k$ times every day,if she decide to fly in road $(u,v,w)$,she will go to $v $from $u$ with $0$ cost.

$\ \ \ \ $Please output the minimum cost from node $1$ to node $n$.

$\ \ \ \ $The first line has a number T,means test case.(For some reasons,T=1.)

$\ \ \ \ $The next line is 2 numbers $n$,$m$.

$\ \ \ \ $Next is m line,there are 5 numbers in every line,which means (a,b,c,d,w).

$\ \ \ \ T=1,1 \le n \le 5*10^4 , 1 \le m \le 10^4,0\le k \le 10,1\le w \le 10^3.$

$\ \ \ \ $Only 1 number in 1 line,which means the minimum cost.

$\ \ \ \ $If node 1 and node n are disconnected,output "CreationAugust is a sb!".

1
5 3 0
1 2 4 5 42
5 5 4 4 468
1 1 3 3 335

42

BestCoder Round #80