Два роки тому ви допомогли з великим успіхом установити в рідному місті першу в країні мережу труб для Flubber. Опитування показують, що всім подобається власний дозатор Flubber на кухні, а тепер підприємливі мешканці знайшли йому застосування. Виявляється, змішаний із водою Flubber допомагає гасити пожежі! Відкриття дуже своєчасне, адже останнім часом неконтрольовані пожежі трапляються напрочуд часто.

Міська рада хоче використати цю властивість, готуючи суміш Flubber і води на центральній станції. Станція під назвою Flubber Department (FD) також матиме спеціальних працівників, навчених виїжджати на місця пожеж і застосовувати оброблений Flubber для приборкання полум’я.

Труби вже прокладені по всьому місту. За їхнім заданим планом визначте, як спрямувати Flubber із фабрики та воду з місцевого джерела трубами до FD.

Обидві рідини течуть тією самою мережею, можливо, навіть тією самою трубою. Усі труби двонапрямні, проте Flubber і вода не можуть текти однією трубою в протилежних напрямках. Якщо вони течуть тією самою трубою в одному напрямку, то неминуче змішуються. Тому вузли оснащені спеціальними мембранами й фільтрами, що дають змогу довільно розділяти й знову поєднувати всі вхідні суміші. Мережа — замкнена система: сумарна швидкість надходження кожної рідини у вузол має дорівнювати швидкості її виходу, крім джерела цієї рідини та місця призначення, FD.

Кожна труба має пропускну здатність. Flubber доволі в’язкий, зі значенням в’язкості $v$, тому труба, яка переносить $v$ літрів води за секунду, переносить лише $1$ літр Flubber за секунду. Для сумішей пропускна здатність змінюється лінійно. Точніше, якщо $c$ — пропускна здатність для води, а $f,w$ — швидкості течії Flubber і води, усі в літрах за секунду, обмеження таке: $v \cdot f + w \le c$.

Найважливіше — збалансувати суміш, що надходить до FD. Ви хочете якомога більше рідини загалом, але також достатньо води, адже нерозбавлений Flubber дуже легкозаймистий, і достатньо Flubber, адже без нього це був би не зовсім «Flubber Department»! Ви придумали формулу «цінності» кінцевої суміші: $F^a \cdot W^{1-a}$, де $F$ і $W$ — швидкості надходження Flubber і води в літрах за секунду, а $a$ — задана стала між $0$ і $1$.

Знайдіть найбільшу досяжну цінність $F^a \cdot W^{1-a}$ і спосіб спрямування обох рідин для її досягнення.

Вхідні дані

Перший рядок містить кількість місць $n$ ($3 \le n \le 200$), кількість труб $p$ ($n-1 \le p \le \frac12 n(n-1)$) та дійсні числа $v$ ($1 \le v \le 10$) і $a$ ($0.01 \le a \le 0.99$). Місця пронумеровані від $1$ до $n$: $1$ — фабрика Flubber, $2$ — джерело води, $3$ — FD. Дійсні числа мають щонайбільше $10$ цифр після десяткової крапки.

Наступні $p$ рядків описують по одній трубі. Кожен містить два цілі числа $j,k$ ($1 \le j < k \le n$), з’єднані місця, і ціле число $c$ ($1 \le c \le 10$), пропускну здатність для води в літрах за секунду.

Жодні дві труби не з’єднують ту саму пару місць. Крім того, мережа гарантовано зв’язна.

Вихідні дані

Спочатку для кожної труби в порядку вхідних даних виведіть дві величини: швидкості течії Flubber і води, від’ємні при течії від $k$ до $j$, так, щоб $F^a \cdot W^{1-a}$ було максимальним. Потім виведіть цей максимум з абсолютною похибкою не більшою за $10^{-4}$.

Якщо розв’язків кілька, приймається будь-який. Усі обмеження —відсутність протилежних напрямків течії рідин в одній трубі, збереження потоку, пропускні здатності та узгодженість побудованого розв’язку із заявленою цінністю— мають виконуватися з абсолютною похибкою не більшою за $10^{-4}$.

Приклади

Вхідні дані 1

6 6 3.0 0.66
2 4 8
4 6 1
3 6 1
4 5 5
1 5 7
3 5 3

Вихідні дані 1

0.000000000 1.360000000
0.000000000 1.000000000
0.000000000 -1.000000000
0.000000000 0.360000000
0.880000000 0.000000000
-0.880000000 -0.360000000
1.02037965897

Вхідні дані 2

5 5 1.0 0.5
1 2 10
2 3 10
3 4 10
4 5 10
3 5 10

Вихідні дані 2

5 0
5 5
4.2 3.14159
4.2 3.14159
-4.2 -3.14159
5