Максимальний потік у неорієнтовному графі

Знайдіть величину максимального потоку у заданому неорієнтовному графі.

Вхідні дані

У вхідному файлі задано один або декілька тестів. Кожен тест починається рядком, у якому міститься число n (2 ≤ n ≤ 100) — кількість вершин графа. У наступному рядку записані три числа s, t і c — номер витоку, номер стоку, і кількість ребер, відповідно. Далі йде c рядків, у кожному з яких міститься три числа: номери з'єднаних ребром вершин та його пропускна здатність — ціле невід'ємне число, яке не перевищує 1000. Між двома парами вершин може бути більше одного ребра, проте петлі не допускаються.

Вхідний файл завершується фіктивним тестом, який складається з одного числа 0, який опрацьовувати не потрібно.

Вихідні дані

Для кожного з тестів виведіть величину максимального потоку.

Приклади