P1343 Earthquake Escape

When the Wenchuan earthquake struck, Sichuan ** High School was in class. As soon as the earthquake occurred, the teachers immediately led $x$ students to evacuate. The whole school can be abstracted as a directed graph with $n$ nodes and $m$ edges. Node $1$ is the classroom, and node $n$ is the safe zone. Each edge can only accommodate a certain number of students; if exceeded, the building would collapse. Due to the large number of people, the principal decided to evacuate in several batches. Only after the first batch has completely evacuated may the second batch start from node $1$. Please help the principal calculate the maximum number of students that can be transported in each batch, and how many batches are needed to transport all $x$ students.

The first line contains three integers $n, m, x$. The next $m$ lines each contain three integers $a, b, c$ ($1 \le a, b \le n$, $0 \le c \le x$), describing an edge: there is an edge from node $a$ to node $b$ that can accommodate $c$ students.

If it is impossible to reach the destination (node $n$), output `Orz Ni Jinan Saint Cow!`. Otherwise, output two integers: the maximum number of students that can be transported in each batch, and the number of batches needed to transport all $x$ students.

[Note] For example, consider the graph ```plain 1 2 100 2 3 1 ``` $100$ students first rush to node $2$, and then go along edge $2 \to 3$ one by one. According to the 2018 "Shen Niu" rules, this is not allowed. In other words, each batch of students must depart from the source simultaneously and arrive at the sink simultaneously. [Constraints] For $100\%$ of the testdata, $0 \le x < 2^{31}$, $2 \le n \le 200$, $1 \le m \le 2000$. Translated by ChatGPT 5