Weighted Shortest Paths Betweenness

Two friends, Xiaoqiang and B, along with many other friends, form a social network which can be modeled as an undirected graph. In this graph, each person is a node and each relationship is an edge. Each person has a influence value denoted by \(a_i\), and each edge has two weights: a length weight \(b_j\) representing the closeness (smaller means closer) and a width weight \(c_j\) representing the communication frequency (larger means more frequent).

For any two people \(s\) and \(t\), they communicate via one of the shortest paths (in terms of the sum of length weights). If there are several shortest paths, we define the width of these paths, \(\sigma_{st}\), as the sum of the product of the width weights along each shortest path. For any vertex \(v\), let \(\sigma_{st}(v)\) be the sum of the products of width weights over all shortest paths from \(s\) to \(t\) that pass through \(v\).

The propagation power of a vertex \(v\) is defined as:

[ R(v)=\sum_{s \neq v \neq t} \frac{a_s a_t \ \sigma_{st}(v)}{\sigma_{st}} ]

In other words, for every ordered pair \((s,t)\) (with \(s\) and \(t\) different from \(v\)), we take the ratio \(\frac{\sigma_{st}(v)}{\sigma_{st}}\) (i.e. the influence of \(v\) in the communication between \(s\) and \(t\)) and weight it by \(a_s\) and \(a_t\). The task is to compute \(R(v)\) for every vertex \(v\) in the graph.

Note: The graph is undirected. There is an edge between nodes \(u\) and \(v\) with length weight \(b\) and width weight \(c\), which contributes multiplicatively to the product of the width weights along a path.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n \leq 10^4,\ 0 \le m \leq 5\times10^4)\), representing the number of nodes and edges, respectively.

The second line contains \(n\) integers: \(a_1, a_2, \ldots, a_n\) \( (1 \leq a_i \leq 10^3)\) representing the influence of each node.

Then \(m\) lines follow, each containing four integers \(u\), \(v\), \(b\), and \(c\) \((1 \le u,v \le n,\ u \neq v,\ 1 \le b, c \le 10^3)\). This denotes an undirected edge between nodes \(u\) and \(v\) with length weight \(b\) and width weight \(c\).

outputFormat

Output \(n\) lines. The \(i\)th line should contain the propagation power \(R(i)\) of node \(i\), formatted to 6 decimal places.

sample

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

0.000000
7.000000
8.000000
0.000000