เมื่อสองปีก่อน คุณช่วยติดตั้งเครือข่ายท่อ Flubber แห่งแรกของประเทศในบ้านเกิดและประสบความสำเร็จอย่างมาก ผลสำรวจแสดงว่าทุกคนชอบมีเครื่องจ่าย Flubber ของตนเองในครัว และตอนนี้พลเมืองที่มีความคิดริเริ่มบางคนค้นพบประโยชน์ของมัน ปรากฏว่า Flubber เมื่อผสมน้ำสามารถช่วยดับไฟได้! นี่เป็นการค้นพบที่ทันเวลา เพราะช่วงนี้เกิดไฟไหม้ที่ควบคุมไม่ได้บ่อยจนน่าแปลกใจ

สภาเมืองต้องการใช้คุณสมบัตินี้ โดยทำส่วนผสม Flubber กับน้ำที่สถานีใจกลางเมือง สถานีนี้เรียกว่า Flubber Department (FD) และจะมีเจ้าหน้าที่เฉพาะทางที่ฝึกให้เดินทางไปจุดเกิดเหตุแล้วใช้ Flubber ที่ผ่านการเตรียมเพื่อควบคุมเพลิง

ท่อถูกติดตั้งไว้ทั่วเมืองแล้ว เมื่อกำหนดแผนผังท่อมา คุณต้องหาวิธีส่ง Flubber จากโรงงานและน้ำจากแหล่งน้ำในท้องถิ่นผ่านท่อไปยัง FD

ของเหลวทั้งสองไหลผ่านเครือข่ายเดียวกัน และอาจผ่านท่อเดียวกันด้วย ทุกท่อใช้ได้สองทิศทาง แต่ Flubber กับน้ำห้ามไหลสวนทางกันในท่อเดียว หากไหลไปทางเดียวกันในท่อเดียวก็จะผสมกันอย่างหลีกเลี่ยงไม่ได้ ดังนั้นแต่ละจุดในเครือข่ายจึงมีเยื่อและตัวกรองพิเศษที่ให้คุณแยกและจัดส่วนผสมที่ไหลเข้ามาใหม่ได้ตามต้องการ เครือข่ายเป็นระบบปิด อัตราไหลรวมของของเหลวแต่ละชนิดที่เข้าจุดใดต้องเท่ากับอัตราที่ออกจากจุดนั้น ยกเว้นที่แหล่งกำเนิดของของเหลวนั้นและปลายทางคือ FD

แต่ละท่อมีความจุ Flubber ค่อนข้างหนืด โดยมีค่าความหนืด $v$ ดังนั้นท่อที่ส่งน้ำได้ $v$ ลิตรต่อวินาทีจะส่ง Flubber ได้เพียง $1$ ลิตรต่อวินาที ความจุสำหรับส่วนผสมของทั้งสองเปลี่ยนแบบเชิงเส้น กล่าวอย่างแม่นยำ หาก $c$ คือความจุสำหรับน้ำ และ $f,w$ คืออัตราไหลของ Flubber และน้ำ โดยทั้งหมดมีหน่วยลิตรต่อวินาที ข้อจำกัดคือ $v \cdot f + w \le c$

สิ่งที่คุณสนใจหลักคือสมดุลของส่วนผสมที่ถึง FD คุณต้องการของเหลวรวมมากที่สุด แต่ก็ต้องมีน้ำเพียงพอ เพราะ Flubber ที่ไม่เจือจางติดไฟง่ายมาก และต้องมี 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