Saving the Princess

As most fairy tales said, unfortunately, our poor princess is trapped in a castle by some bad guys again.

Simple word, we need save her again, because she is so beautiful and graceful that we love her so much. Our country was composed of N cities and M undirected roads, the princess was in the city A, and we were in city 0, the capital. Obviously, only we arrive at the city A first can we save the princess.
However, it’s not a shortest path problem because we had extremely enough time to spend among the roads. What matters was whether we could arrive at the city A.

Perhaps a strange problem, but it’s reasonable because we need food and water while travelling from one city to another, or we just would be died before we can see the princess. To make the situation less complicated, we assumed we always consumed two units of food and one unit of water when we were walking, just like a coefficient multiply the distance we had walked.

But the condition left for us is a little annoyed. As our country was very poor, we could only purchase the food in the capital. What’s more, at any time, the sum of food units and water units we carried can’t exceed the capacity S.
Oh, don’t be despair, please. Also some not too bad news was here. We could rest and collect water as much as possible at any city, and in each city, there were plenty of storages to store food for our later use.

Now, to save our lovely and pitiful princess, how much food we have to purchase in the capital at least?

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with four integers N, M, S, A. Their meanings are the same as the description.
Then M lines follow, each line contains three integers Ai, Bi, Ci, indicating an undirected road from Ai to Bi whose length was Ci.

Technical Specification

1. 1 <= T <= 50
2. 2 <= N <= 1000
3. 1 <= M <= 50000
4. 1 <= S, Ci <= 100000
5. 1 <= A < N
6. 0 <= Ai, Bi < N, Ai != Bi

For each test case, output the case number first, then the minimum units of food if you can arrive to the city A, otherwise output “Poor princess, we will miss you!”

3
2 1 5 1
0 1 1
2 1 5 1
0 1 2
4 5 20 3
0 1 3
0 2 4
2 3 5
1 3 6
0 3 7

Case 1: 2
Case 2: Poor princess, we will miss you!
Case 3: 30

iSea@WHU

The 6th Central China Invitational Programming Contest and 9th Wuhan University Programming Contest Final