小祥平時的工作是在樂團裡彈鋼琴，但是彈琴賺的錢不夠多，除了在客服打工還有陪初華散步外，小祥會當 F1 的賽車手，小祥的賽車叫阿倍姆基。

因為小祥樓樓上的鄰居是從昨天開始才看 F1，所以小祥要講解 F1 賽車的規則：有 $N$ 個站點與 $M$ 條雙向賽道，每條雙向賽道連接兩個站點 $u_i,v_i$，並且長度為 $w_i$ 公里。所有站點是連通的，代表任兩個站點可以經過一系列賽道到達。

小祥要從站點 $1$ 開她的賽車阿倍姆基到站點 $N$，她會攜帶 $L$ 罐氮氣，每罐氮氣會有一個係數 $a_i$，代表用了這罐氮氣後賽車 $1$ 公里只要開 $a_i$ 秒。小祥會從第 $1$ 罐氮氣依序往後使用，每次要經過一個賽道時，假設目前用完 $k-1$ 罐氮氣輪到第 $k$ 罐氮氣，小祥可以做以下的動作：丟掉 $p$（$0\le p$） 罐氮氣，並使用目前的氮氣 $a_{k+p}$ 開過賽道，一罐氮氣在開完一個賽道後就會消耗完畢，下一次使用時會從 $a_{k+p+1}$ 開始看。如果過程中不在站點 $N$ 且已經用完 $L$ 罐氮氣了，代表阿倍姆基卡在原地，小祥會被罰錢，為了不讓小祥被罰錢，$N-1\le L$，代表小祥在不丟掉氮氣的情況下，可以從站點 $1$ 開到站點 $N$。

小祥的成績計算方式是開過的賽道裡花的時間最久的那個，也就是假設小祥在從站點 $1$ 開到站點 $N$ 的過程中開過了 $S$ 條賽道，編號分別是 $x_1\sim x_S$，使用氮氣的編號分別是 $y_1\sim y_S$，那她的成績會是 $\max\limits_{i=1}^ S(w_{x_i} \cdot a_{y_i})$。
為了贏過東京阿儂大車隊，小祥想要成績越小越好，請你幫幫她算出最小可以是多少！