Максимальний потік мінімальної вартості

Задано орієнтовний граф, кожне ребро якого має пропускну здатність та варітсть.

Знайдіть максимальний потік мінімальної вартості з вершини під номером 1 у вершину під номером n.

Вхідні дані

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

Вихідні дані

У вихідний файл виведіть одне число - ціну максимального потоку мінімальної вартості з вершини під номером 1 у вершину під номером n. Відповідь не перевищує 2^63-1. Гарантується, що у графі немає циклів від'ємної вартості.

Приклади