在游戲《星際爭(zhēng)霸 II》中，戰(zhàn)列巡航艦作為人類的終極作戰(zhàn)武器，在后期 以及一些中期戰(zhàn)術(shù)中發(fā)揮著空中堡壘的作用，其 “戰(zhàn)術(shù)跳躍” 技能能讓其在游戲 中期在敵軍基地上空造成打擊之后在血量較低時(shí)撤離，進(jìn)行無(wú)戰(zhàn)損騷擾，在人 類 vs 異蟲對(duì)抗中經(jīng)常用來(lái)壓制異蟲中期的發(fā)展。
你在玩一個(gè)游戲，游戲中有 n 個(gè)地點(diǎn)和 m 條單向時(shí)空航道。每條時(shí)空航道形如 (u, v, w, x)，其中 u，v 表示這條時(shí)空航道的起點(diǎn)終點(diǎn)，w 表示通過(guò)這條航道需要的時(shí)間(注意這個(gè)時(shí)間是現(xiàn)實(shí)當(dāng)中游戲者的時(shí)間也是游戲內(nèi)的時(shí)間)，x表示這條航道使用的頻繁程度。時(shí)空航道不會(huì)成環(huán)，但可能會(huì)有兩條航道的起別為x ,x ,x ,···x，那么選擇第i個(gè)航道的概率就是∑ xi 。你的目的是在L 123 k kj=1xj點(diǎn)相同同時(shí)終點(diǎn)也相同。游戲開始的時(shí)候，你的戰(zhàn)列巡航艦到達(dá)了地點(diǎn) 1，每當(dāng)你到達(dá)一個(gè)地點(diǎn)的時(shí)候，戰(zhàn)艦的電腦會(huì)按照每個(gè)起點(diǎn)為該地點(diǎn)的時(shí)空航道的頻繁程度隨機(jī)選擇一個(gè)航道并花費(fèi) w 單位時(shí)間到達(dá)該航道的終點(diǎn)。具體來(lái)說(shuō)，對(duì)于一個(gè)時(shí)間點(diǎn) u，假如有 k 個(gè)起點(diǎn)為該地點(diǎn)的時(shí)空航道，他們的頻繁程度分別為x ,x ,x ,···x，那么選擇第i個(gè)航道的概率就是∑ xi 。你的目的是在L 123 k kj=1xj單位游戲時(shí)間內(nèi)到達(dá)一個(gè)沒(méi)有任何以該地點(diǎn)為起點(diǎn)的時(shí)空航道的地點(diǎn)。當(dāng)然你 可以在到達(dá)某一個(gè)地點(diǎn)時(shí)重新開始游戲，如果你重新開始這個(gè)游戲，你就能回 到游戲開始的那一刻(即 1 號(hào)地點(diǎn))并重置游戲內(nèi)的時(shí)間(即你又可以有 L 單 位的時(shí)間去跳躍了)，你也可以在沒(méi)有任何以該地點(diǎn)為起點(diǎn)的地點(diǎn)重新開始，且 無(wú)次數(shù)限制。你需要最小化你在現(xiàn)實(shí)中花費(fèi)的時(shí)間。當(dāng)然在你運(yùn)氣足夠好的情 況下，你一定可以達(dá)成游戲目標(biāo)。
保證一定有至少一條以 1 號(hào)地點(diǎn)為起點(diǎn)的航道。 請(qǐng)閱讀樣例以更清晰地理解題意。
第一行三個(gè)正整數(shù) n，m，L。
接下來(lái) m 行，每行四個(gè)正整數(shù) u，v，w，x。
(2 ≤ n ≤ 100，1 ≤ m ≤ 200，w, x ≤ 100，0 ≤ L ≤ 109)
一行一個(gè)浮點(diǎn)數(shù)表示答案，令你的答案為 a，標(biāo)準(zhǔn)答案為 b，如果滿足 |a?b|/max(1,b) ≤ 10?9(即絕對(duì)誤差或者相對(duì)誤差不超過(guò) 10?9)即為正確。
3 2 3 1 2 2 1 1 2 4 1
6