Два года назад вы помогли с большим успехом установить в родном городе первую в стране сеть труб для 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