Задано орієнтовний граф, кожне ребро якого має пропускну здатність та варітсть. Знайдіть максимальний потік мінімальної вартості з вершини під номером \textbf{1} у вершину під номером \textbf{n}. \InputFile Перший рядок вхідного файлу містить \textbf{n} та \textbf{m} - кількість вершин та кількість ребер графа (\textbf{2} ≤ \textbf{n} ≤ \textbf{100}, \textbf{1 }≤ \textbf{m} ≤ \textbf{1000}). Наступні \textbf{m} рядків містять по чотири цілих числа числа: номери вершин, які з'єднує відповідне ребро графа, його пропускну здатність та його вартість. Пропускні здатності та вартості не перевищують \textbf{10^5}. \OutputFile У вихідний файл виведіть одне число - ціну максимального потоку мінімальної вартості з вершини під номером \textbf{1} у вершину під номером \textbf{n}. Відповідь не перевищує \textbf{2^63-1}. Гарантується, що у графі немає циклів від'ємної вартості.