Задан ориентированный граф, каждое ребро которого обладает пропускной способностью и стоимостью.
Найдите максимальный поток минимальной стоимости из вершины с номером 1 в вершину с номером n.
Первая строка входного файла содержит n и m - количество вершин и количество ребер графа (2 ≤ n ≤ 100, 1 ≤ m ≤ 1000). Следующие m строк содержат по четыре целых числа числа: номера вершин, которые соединяет соответствующее ребро графа, его пропускную способность и его стоимость. Пропускные способности и стоимости не превосходят 10^5.
В выходной файл выведите одно число - цену максимального потока минимальной стоимости из вершины с номером 1 в вершину с номером n. Ответ не превышает 2^63-1. Гарантируется, что в графе нет циклов отрицательной стоимости.