Оптимальный поток величины 1
Дан ориентированный граф из n вершин и m ребер. Вершина 1 является истоком, вершина n - стоком. Каждому ребру приписана некоторая цена.
Найдите в данной сети оптимальный поток величины 1, т.е. поток величины 1, имеющий наименьшую стоимость. Цены ребер могут быть отрицательными, однако известно, что граф не содержит циклов отрицательного веса. Пропускные способности вам не заданы, про них известно, что они не меньше 1.
Входные данные
В первой строке заданы числа n и m (2 ≤ n ≤ 1000, 0 ≤ m ≤ 10000). Дальше идет m строк с тройками целых чисел x, y, p - ребро из x в y имеет цену p (1 ≤ x, y ≤ n, -1000 ≤ p ≤ 1000). В графе могут быть петли и кратные ребра.
Выходные данные
Выведите одно целое число - стоимость оптимального потока величины 1. В случае если в сети не существует потока величины 1, выведите NO.