D. Цикл через заданную вершину

Определите, проходит ли через вершину $v$ хотя бы один цикл отрицательного веса.

Обычный Форд — Беллман отвечает лишь на вопрос «есть ли отрицательный цикл где-нибудь», и через $v$ он проходить не обязан. Нужна динамика по числу рёбер — та же, что в классной задаче O.

Пусть $f_k[i][j]$ — наименьший вес маршрута ровно из $k$ рёбер. Тогда через $v$ проходит отрицательный цикл тогда и только тогда, когда $f_k[v][v] < 0$ для какого-нибудь $k$ от 1 до $n$.

Больше $n$ рёбер перебирать незачем: если замкнутый маршрут отрицательного веса через $v$ существует, то существует и такой, где вершины не повторяются, а значит рёбер в нём не больше $n$.

Стоит это $O(n^4)$, что при $n \le 60$ вполне посильно.

Первая строка содержит числа $n$ ($1 \le n \le 60$), $m$ ($0 \le m \le 2000$) и $v$.

Далее идут $m$ строк с рёбрами: начало, конец и вес ($|w| \le 1000$). Возможны кратные рёбра и петли.

Одно слово: YES или NO.