Лимит времени 1с.
Построили новую школу. Школа содержит N кабинетов, пронумерованных от 1 до N, между некоторыми из них двери. Когда ученик проходит через дверь, он получает определенное количество знаний. Вход в школу находится в кабинете 1, а выход в N. Каждый ученик проходит школу ровно один раз и поступает в определенный вуз в зависимости от набранных баллов (при входе в школу этот балл равен нулю). Ваша задача показать лучший результат.
Входные данные
Первая строка входного файла содержит целые числа N (1≤ N≤2000) — количество кабинетов и M (1≤M≤10000) количество дверей. В каждом из следующих M строк содержится описание двери: номер кабинета, из которого и в который они ведут, а также целое число, которое определяет количество знаний полученных при прохождении через дверь (это число по модулю не превышает 10000). Двери могут вести из кабинета в тот самый кабинет, между двумя кабинетами может быть больше чем одна дверь.
Исходные данные
В выходной файл выведите "yes" — если можно получить неограниченно большой запас знаний, "no" — если школу пройти нельзя, и максимальное количество знаний противном случае.

Что понятно:
1) задан ориентированный граф
2) если нет петель и циклов, граф — связный, тогда 1 — исток, N — сток, и решение получаем алгоритмом "нахождения максимального потока"
3) если есть петли или цикл(проверка алгоритмом bfs или dfs), где сумма по дугах положительна — тогда "yes"
4) если между 1 и N нет пути (алгоритм bfs или dfs), тогда "no".

Что вызывает вопрос: если применить все эти алгоритмы, то для "большого" графа предварительная проверка на ацикличность, проверка связности могут занять много времени. На чем можно (в рамках поставленной задачи) — сэкономить?