Dina's Hunting Expedition

Dina the lion patrols her territory which consists of a den (node 0) and n distinct hunting grounds (nodes 1 through n). There are bidirectional roads connecting some pairs of these locations. Each road connecting node u and node v costs \( h_{u,v} \) units of energy and \( t_{u,v} \) units of time to traverse.

Each hunting ground i has an associated probability \( p_i \) of a successful hunt, and every time Dina hunts at ground i she spends \( h_i \) energy and \( t_i \) time. Every morning, starting from her den, Dina selects uniformly at random one of the hunting grounds directly connected to the den and travels there. Upon arriving at a hunting ground, she carries out one hunt (thus incurring the hunting cost). Whether or not she has already exceeded her limits, if she reaches a hunting ground she always hunts before assessing her condition.

After a hunt at a hunting ground \( u \) (with updated accumulated energy \( E \) and time \( T \)), one of the following happens:

1. If the hunt is successful (this happens with probability \( p_u \)), or if
   \(E \ge H\) or \(T \ge T\) (the limits for energy and time, respectively) after the hunt, or if the current hunting ground \( u \) is adjacent only to the den (i.e. it has no adjacent hunting ground other than node 0), then Dina returns immediately to her den along a route which minimizes the total time. In case of ties she chooses the route with the minimum energy consumption. While returning she does not hunt.
2. Otherwise (i.e. the hunt failed, and neither limit is reached and there is at least one adjacent hunting ground other than the den), she selects uniformly at random one of the hunting grounds adjacent to \( u \) (excluding the den) and travels there. The travel incurs its corresponding energy and time cost. Upon arrival she hunts exactly once and then proceeds as above.

The journey starting from the den and ending when Dina returns to the den (triggered by either a successful hunt, reaching/exceeding one of the limits, or having no available adjacent hunting ground from her current location) is defined as a hunting expedition.

Your task is to compute the expected total energy and time that Dina expends in one hunting expedition.

Note on the return path: When returning to the den, Dina always takes the path with minimum total time. If there is more than one such path, she takes the one with minimum energy expenditure. Any travel between locations does not trigger a condition check even if the energy/time consumption exceeds the limits. The only time the limits are checked is immediately after a hunt at a hunting ground, and when arriving at the den.

All formulas are in \( \LaTeX \) format.

inputFormat

The first line of input contains four integers: n, m, H and T, where n (\(1 \le n\le N\)) is the number of hunting grounds, m is the number of bidirectional roads, H is the energy limit, and T is the time limit.

The following m lines each contain four integers \( u \), \( v \), \( h_{u,v} \), and \( t_{u,v} \) indicating that there is a road between locations \( u \) and \( v \) (\( 0 \le u,v \le n \); node 0 is the den) that requires \( h_{u,v} \) energy and \( t_{u,v} \) time to traverse.

The next n lines describe the hunting grounds 1 through n. The i-th of these lines contains a real number \( p_i \) and two integers \( h_i \) and \( t_i \), where \( p_i \) (\( 0 \le p_i \le 1 \)) is the probability that a hunt at ground \( i \) is successful, \( h_i \) is the energy expended on a hunt at ground \( i \), and \( t_i \) is the time spent.

You may assume that the graph is connected.

outputFormat

Output two real numbers: the expected total energy expenditure and the expected total time consumption for one hunting expedition. Your answer is accepted if each number has an absolute or relative error no more than \(10^{-6}\).

sample

2 2 100 100
0 1 1 2
0 2 2 1
0.5 1 1
0.3 2 2

4.500000 4.500000