Mr. Hu P29558

[r]

Mr. Hu makes a living by helping the tourists of the little town of Tangkou in every imaginable way. However, to do so, he first needs to bring as many customers as possible to his tiny restaurant (which is in fact his home). When a group of tourists arrives at Tangkou, Mr. Hu is immediately ringed at home by local informers. He then rides his motorbike and rushes to meet the group. Afterwards, as many tourists as the narrow streets of Tangkou permit are softly conducted by Mr. Hu to his home by walk.

Mr. Hu’s business is so successful that he is planning to move it to Shanghai. But Shanghai has so many streets, some of them so long or so wide, that he needs to find the fastest path from home to a certain street intersection, and also the widest path from that intersection back home. (The wideness of a path is the minimum of the wideness of its streets.) Can you help him?

Input

Input is all integers, and consists of several cases, each one beginning with a line with n, m, h, g and p: n is the number of street intersections (numbered from 0 to n−1), m ‍is the number of streets connecting them, h is the intersection number of Mr. Hu’s home, g is the intersection number of the group of tourists, and p is the number of tourists. Assume 2 ≤ n ≤ 10⁴, 1 ≤ m ≤ 10n, that h and g are different, and 1 ≤ p ≤ 10⁴.

Then m lines follow, one for every street, each with four numbers x, y, t_xy and w_xy. The first two are the intersection numbers of the beginning and of the end of the street. t_xy is the time to drive the street from x to y (or from y to x, assume no difference). A special value of −1 for t_xy indicates that it is not allowed to drive the street connecting x to y. w_xy is the number of people, Mr. Hu included, that can walk at the same time the street from x to y (or from y to x). Suppose 0 ≤ x < y < n, 1 ≤ t_xy ≤ 10⁴, and 1 ≤ w_xy ≤ 10⁴.

There is no more than one street connecting two intersections. There is always at least one path from h to g. A special case with n = m = h = g = p = 0 marks the end of input.

Output

For every case, print the optimal time to drive from h to g, and also the maximum number of tourists that Mr. Hu can bring home.