Problem : 57 - 那時，我位於世界的盡頭

Problem Statistics

Solved Member: 20　　Submission: 333　　User Tried: 22

Statement:

あの時、確かにおまえは世界の果てにいた(那時，你正在世界的盡頭)。

你正位於世界盡頭的樹海。

你喜歡大自然，所以你到樹海來玩。樹海有n個地點可以遊玩，每個地點好玩的程度並不太一樣。
但是樹海也是非常恐怖的，遊玩地點之間有恐怖的單向道路相連著，每條道路有它獨立的驚悚度。我們定義一趟旅程的驚悚度為路途中所經過道路的驚悚度總和。

你目前在點1，你希望至少繞過除了原點以外的一個點再回來原地，並且除了起點和終點相同以外所有點是不重複的。並且你希望好玩程度與驚悚程度的比值越大越好，這樣你會覺得這趟旅途比較值得。

有 n 個點 m 條邊，每個點有點權(有趣程度)，每條邊有邊權(驚悚程度)。你希望隨便找一條環，使得 $\frac{\sum 有趣程度}{\sum 驚悚程度}$ 最大。每個點可以重複經過，但是有趣程度只能算一次。

Input:Output:

第1行有2個數字n($n \leq 1000$)以及m($m \leq 5000$)，代表地點數以及道路數。
第2行開始後n行分別代表點1到點n的好玩程度，保證所有點的好玩程度為正且<=1000。
接著有m行，每行有3個數字i,j,k，代表i到j有一條驚悚度為k($1 \leq k \leq 1000$)的路線存在。

輸出只有1行，代表最佳路線的好玩程度以及驚悚程度的比值，請輸出到小數點以下第二位。
若不存在這樣的一條路線，請輸出"0"。

Sample Input:Sample Output:

5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2

6.00

Source:

USACO 2007 Dec. Gold

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1	1000ms	65536kb	10
2-1	1000ms	65536kb	10
2-2	1000ms	65536kb
3-1	1000ms	65536kb	10
3-2	1000ms	65536kb
4-1	1000ms	65536kb	10
4-2	1000ms	65536kb
5	1000ms	65536kb	10
6	1000ms	65536kb	10
7	1000ms	65536kb	10
8	1000ms	65536kb	10
9	1000ms	65536kb	10
10	1000ms	65536kb	10