Description

Xiaoqiang and Mr. B are good friends.

Besides Mr. B, Xiaoqiang also has many good friends, such as Jie Mei.

Besides Xiaoqiang, Mr. B also has many good friends, such as Mr. R. They also have many mutual friends, such as Xiaohua, Cong Niang, and another $3$ people.

Mr. B realized that relationships between people can be viewed as an undirected graph: each person is a vertex, and each relationship is an edge.

Different people have different influence in society. Let $a_i$ denote the influence of the $i$-th person.

Relationships between people also vary: they may be very close, or just casual acquaintances; they may stick together every day, or contact only once a year. Therefore, we use a length edge weight $b_j$ to describe the closeness of the two users connected by the $j$-th edge: the smaller the length, the closer they are. At the same time, we use a width edge weight $c_j$ to describe the communication frequency of the two users connected by the $j$-th edge: the larger the width, the more frequently they communicate.

The length of a path is the sum of the length edge weights of all edges on the path. The width of a path is the product of the width edge weights of all edges on the path.

When two people $s$ and $t$ want to communicate, they will choose a shortest path (in terms of length). Since there may be multiple shortest paths, we define the width of the shortest paths from $s$ to $t$ as $\sigma_{st}$, which is the sum of the widths of all shortest (minimum-length) paths from $s$ to $t$. Also, let $\sigma_{st}(v)$ denote the sum of the widths of all shortest paths from $s$ to $t$ that pass through $v$, i.e., the influence of $v$ on $s,t$.

The spreading power $R(v)$ of a person $v$ in the graph is defined as:

$$R(v)=\sum\limits_{s \ne v \ne t} \frac{a_s a_t \sigma_{st}(v)}{\sigma_{st}}$$

That is, for all ordered pairs of vertices in the graph that do not include $v$, compute the influence of $v$ on that pair divided by the total width of the shortest paths for that pair, then multiply by the influences of the two endpoints, and finally sum the results over all such pairs to obtain the spreading power of the vertex.

Mr. B wants to quickly know the spreading power of every vertex in the graph. When he asked Xiaoqiang, Xiaoqiang said: “I have a brilliant method, but the statement is too short to write it down.”

Do you know how to do it?

Input Format

The first line contains $2$ positive integers $n$ and $m$, representing the number of vertices and the number of edges in the graph.

The next $n$ lines: the $i$-th line contains one non-negative integer $a_i$, representing the influence of the $i$-th person.

The next $m$ lines: the $j$-th line contains $3$ integers $x_j$, $y_j$, $b_j$ and one real number $c_j$, meaning there is an edge between vertex $x_j$ and vertex $y_j$ with length edge weight $b_j$ and width edge weight $c_j$.

Output Format

Output $n$ lines. The $i$-th line contains one real number $R(i)$, representing the spreading power of the $i$-th vertex in the graph.

5 5
1
2
3
4
5
1 2 2 0.7
3 4 2 0.9
1 3 1 1.1
2 4 1 1.3
4 5 10 2

4.762887
8.621053
9.378947
67.237113
0.000000

Hint

Scoring

We will compare each number in the output file with the reference answer. If the relative error or absolute error of that number does not exceed $10^{-6}$, it will be judged correct. For numbers whose reference answer is $0$, the absolute error must not exceed $10^{-6}$ to be judged correct.

If the number of correct outputs is $q$, then your score on that test point is $\left\lfloor\ 5(\dfrac{q}{n})^7 \right\rfloor$.

Constraints

For test points $1,2,3,4$, $n \le 100$.

For test points $5,6,7,8$, all $b_j=1$.

For test points $9,10,11,12$, $m=n-1$.

For test points $1,3,5,7,9,11,13,15,17,19$, all $a_i=1$.

For test points $1,2,5,6,9,10,13,14,17,18$, all $c_j=1$.

For all testdata, $n \le 1000$, $m \le 4 \times 10^3$, $0<a_j \le 255$, $0<b_j \le 15$, $0.5 \le c_j \le 2$, and the fractional part of $c_j$ has at most $12$ digits. The graph is guaranteed to be connected.

Translated by ChatGPT 5