Cost Performance Flow

Yayoi is an expert at saving money. She never picks an item just because it is cheap, and her motto is "cost performance". That is one reason she cooks so well with bean sprouts. Word of her thrift has spread, so people keep asking her to cut costs of all kinds. This time the job is optimizing a network flow.

Consider a directed graph $G = (V, E)$, where $V = \{1, 2, \dots, |V|\}$ is the vertex set and $E \subset V \times V$ is the edge set. Every edge $e$ has a capacity $u(e)$ and a cost $c(e)$. For two vertices $s$ and $t$, a function $f_{s,t} : E \to \mathbb{R}$ is an $s$-$t$ flow when both of the following hold.

• $0 \le f_{s,t}(e) \le u(e)$ for every edge $e \in E$.
• For every vertex $v \in V \setminus \{s, t\}$, the flow entering $v$ equals the flow leaving $v$, that is $\sum_{e = (w, v) \in E} f_{s,t}(e) = \sum_{e = (v, w) \in E} f_{s,t}(e)$.

The value and the cost of $f_{s,t}$ are defined as follows.

$F(f_{s,t}) = \sum_{e = (s, v) \in E} f_{s,t}(e) - \sum_{e = (v, s) \in E} f_{s,t}(e), \qquad C(f_{s,t}) = \sum_{e \in E} f_{s,t}(e) c(e)$

Optimizing a network flow usually means minimizing the cost among the maximum flows. Yayoi judges by cost performance instead. Let $F_{\max} = \max_f F(f)$ be the maximum value over all $s$-$t$ flows $f$, and define the balance function of an $s$-$t$ flow $f_{s,t}$ as follows.

$B(f_{s,t}) = C(f_{s,t})^2 + (F_{\max} - F(f_{s,t}))^2$

Yayoi regards the flow that minimizes $B$ as the one with the best cost performance. Compute the minimum of $B(f_{s,t})$ over all $s$-$t$ flows.

The input is a single test case. The first line has two integers separated by one space: the number of vertices $N$ ($2 \le N \le 100$) and the number of edges $M$ ($1 \le M \le 1\,000$). The second line has two vertices $s$ and $t$ ($1 \le s, t \le N$, $s \ne t$). Each of the following $M$ lines describes one edge with four integers $a_i$, $b_i$, $u_i$, $c_i$. The $i$-th edge goes from $a_i$ to $b_i$ ($1 \le a_i, b_i \le N$), its capacity is $u_i$ ($1 \le u_i \le 100$), and its cost is $c_i$ ($1 \le c_i \le 100$). For every $i$, $a_i \ne b_i$, and $(a_i, b_i) \ne (a_j, b_j)$ whenever $i \ne j$.

Print the minimum of $B$ on one line as an irreducible fraction. Precisely, print "u/d", where $u$ is the numerator and $d$ is the denominator. Both $u$ and $d$ must be non-negative integers whose greatest common divisor is 1. The answer is always a rational number. If the minimum is 0, print "0/1".