P2153 [SDOI2009] Morning Run

Elaxia has recently become obsessed with karate. He set up a fitness plan for himself, such as push-ups and sit-ups, but so far, the only thing he has stuck with is the morning run. You are given a map of the area near the school, containing $N$ intersections and $M$ streets. Elaxia can only run from one intersection to another, and streets intersect only at intersections. Every day, Elaxia runs from the dorm to the school. The dorm is numbered $1$, and the school is numbered $N$. Elaxia’s morning runs follow a cycle (spanning several days). Because he dislikes repeating routes, within one cycle, the routes chosen on different days must not intersect at any intersection; the dorm and the school are not considered intersections. Elaxia’s stamina is limited. He wants the total distance run in one cycle to be as short as possible, but he also wants the number of days in the training cycle to be as large as possible. Besides practicing karate, Elaxia spends the rest of his time studying and looking for “MM” (meimei), so he asks you to design a morning running plan that meets his requirements. There may exist an edge $1 \rightarrow N$. In that case, this edge can be used at most once.

The first line contains two integers $N, M$, the number of intersections and streets. The next $M$ lines each contain three integers $a, b, c$, indicating there is a directed street from intersection $a$ to intersection $b$ with length $c$.

Output one line with two integers: the maximum number of days in a cycle, and, among all plans achieving this maximum, the minimal total distance.

- For 30% of the testdata, $N \le 20$, $M \le 120$. - For 100% of the testdata, $2 \leq N \le 200$, $1 \leq M \le 2 \times 10^4$, $1 \le c \le 10^4$. Translated by ChatGPT 5