Problem Description

Taro is given a directed graph with $ N $ vertices and $ M $ edges. This graph may have multiple edges, but it does not have any self-loops. Each edge $ e $ has a given value $ c_e $.

Taro can assign real numbers to $ N $ variables $ a_v $ for each vertex $ v $ and a variable $ T $. He wants to minimize $ T $ while satisfying the following condition:

• Condition: For any edge $ e $ with the starting vertex $ u $ and the ending vertex $ w $, $a_u + c_e \leq a_w + T$ must hold.

Additionally, some of the $ a_v $ values are already fixed for certain vertices $ v $ and cannot be reassigned.

Output the minimum possible value of $ T $ as a real number. If it can be made arbitrarily small, output a single character "#".

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ K $ $ v_1 $ $ val_1 $ $ v_2 $ $ val_2 $ : $ v_K $ $ val_K $ $ u_1 $ $ w_1 $ $ c_1 $ $ u_2 $ $ w_2 $ $ c_2 $ : $ u_M $ $ w_M $ $ c_M $

• All numbers in the input are integers.
• The first line contains $N(1 \leq N \leq 2,000)$, $M(1 \leq M \leq 2,000)$, and $K(0 \leq K \leq N)$ separated by spaces. $ N $ and $ M $ represent the number of vertices and edges in the given graph, respectively. $ K $ is the number of vertices with predetermined $ a $ values.
• The next $ K $ lines provide information about the vertices with predetermined $ a $ values. The $ i $-th line contains $v_i\ (1 \leq v_i \leq N)$ and $val_i\ (-10^5 \leq val_i \leq 10^5)$ separated by spaces, indicating that $ a_{v_i} = val_i $. Assume $ v_i $ are distinct.
• The next $ M $ lines provide edge information for the graph. The $ i $-th line contains $u_i(1 \leq u_i \leq N)$, $w_i(1 \leq w_i \leq N)$, and $c_i(-10^5 \leq c_i \leq 10^5)$ separated by spaces, indicating a directed edge from vertex $ u_i $ to $ w_i $. Also, $u_i \neq v_i$ holds.

Output Format

Output the minimum value of $ T $ as a real number according to the problem statement. If it can be made arbitrarily small, output a single character "#".

When the answer is a real number, the error is acceptable within an absolute or relative error of $ 10^{-5} $.

Output to the standard output and include a newline at the end.

Sample Input and Output

Sample Input #1

3 3 0
1 2 3
2 3 4
3 1 5

Sample Output #1

4.000000

Sample Input #2

3 2 3
1 1
2 2
3 3
1 2 3
2 3 4

Sample Output #2

3.000000

Sample Input #3

10 8 0
8 7 5
6 8 -3
10 1 2
1 5 -8
4 7 -2
5 4 -7
10 5 1
1 5 7

Sample Output #3

#

Notes/Hints

Sample Explanation 1

• $ a $ can be assigned as $ a_1=0, a_2=-1, a_3=-1 $.

Sample Explanation 2

• Since all $ a $ values are already determined, the minimum value of $ T $ can be quickly determined.

Sample Explanation 3

• Be aware that the graph may have multiple edges.

见题面 Input 部分

见题面 Output 部分