背景

阿祁每次都被臨末嘲諷，因為臨末太電了，不過最近他有個計畫，他想出一題難題來考倒臨末，然而這似乎有點困難。

阿祁：怎麼辦，我只會出水題…嗚嗚嗚

Ststone：我聽說臨末不會圖論題哈哈

lai alan：我好像也有聽說過這件事，只是不知道是不是真的

神秘人物：是真的吧，他每次CF遇到圖論都燒雞

阿祁：好欸，那出題了！

題目敘述

給你一個$N$個點(編號$1$ ~ $N$)、$M$個邊的無向簡單圖，以及一正整數$K$，對於第$i$個邊，有個連結$U_i$、$V_i$且權重為$W_i$的雙向邊，請你考慮每個以$1$為起點、$N$ 為終點、途中不經過重複點之路徑，假設某個路徑經過了$p$個邊，則我們把這$p$個邊的權重以$C_1,\ C_2,\ C_3,\ ... ,\ C_p$的方式表示，接著我們要決定一個長度為$p$的正整數序列$X_1,\ X_2,\ X_3,\ ... ,\ X_p$，使得$\sum_{i = 1}^{p}X_i=K$，現在我們想讓$\sum_{i = 1}^{p}\frac{C_i}{X_i}$的值越小越好(注意這可能是浮點數)，這個值我們稱做磷酸距離，簡單來說就是要你找條路徑、以及長度和經過邊的數量相等的序列$X$，使得$\sum_{i = 1}^{p}\frac{C_i}{X_i}$最小，請試著找到這個值，保證答案$\ ≤ 10^6$。

測資範圍

$\color{black}{1 ≤ N, M ≤ 500}$

$\color{black}{min(N-1, M) ≤ K ≤ 1000}$

$\color{black}{1 ≤ U_i, V_i ≤ N}$

$\color{black}{1 ≤ W_i ≤ 10^5}$

$\color{black}{ans ≤ 10^6}$