לפני שנתיים עזרת בהצלחה רבה להתקין בעיר הולדתך את רשת צינורות ה־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