# Mr. Hu

![image](hu.jpg){width="4.4cm"}

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 \le n \le 10^4$, $1 \le m \le 10n$, that $h$ and
$g$ are different, and $1 \le p \le 10^4$.

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 \le x < y < n$,
$1 \le t_{xy} \le 10^4$, and $1 \le w_{xy} \le 10^4$.

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.

## Problem information

Author: Salvador Roura

Generation: 2026-01-25T10:39:24.068Z

© *Jutge.org*, 2006--2026.\
<https://jutge.org>
