Problem Description
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≤x≤b,c≤y≤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 vfrom u with 0 cost.
Please output the minimum cost from node 1 to node n.
Input
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≤n≤5∗104,1≤m≤104,0≤k≤10,1≤w≤103.
Output
Only 1 number in 1 line,which means the minimum cost.
If node 1 and node n are disconnected,output "CreationAugust is a sb!".
Sample Input
1
5 3 0
1 2 4 5 42
5 5 4 4 468
1 1 3 3 335
Sample Output
42
