题目描述

小强和 B 君是好朋友。

小强除了 B 君还有很多好朋友，比如洁妹。

B 君除了小强也还有很多好朋友，比如R君。他们还有很多共同的好朋友，比如小花，葱娘和其他 \(3\) 个人。

B 君发现，人与人之间的关系可以看成是一个无向图，每个人看成一个点，人与人之间的关系看成一条边。

不同的人在社会中的号召力不一样，我们用 \(a_i\) 来表示第 \(i\) 个人的号召力。

人与人之间的关系也各不相同，可能非常友好，可能只是泛泛之交；可能天天腻在一起，可能一年才联系一次。为此，我们用长度边权 \(b_j\) 来刻画第 \(j\) 条边对应的两个用户的亲密程度，长度约小，双方就越亲密；同时，我们用宽度边权 \(c_j\) 来刻画第 \(j\) 条边对应的两个用户的交流频率，宽度越大，两个人沟通的频率也就越高。

一条路径的长度指的是这条路径上的所有边的长度边权之和，一条路径的宽度指的是这条路径上的所有边的宽度边权的乘积。

当两个人 \(s\) 和 \(t\) 想要交流的时候，他们会选择长度最短的路径来交流。由于最短路可能有多个，我们称 \(s\) 到 \(t\) 的最短路的宽度为 \(\sigma_{st}\)，是所有 \(s\) 到 \(t\) 的长度最短的路径的宽度和。同时，我们用 \(\sigma_{st} (v)\) 表示所有从 \(s\) 到 \(t\)，且经过 \(v\) 的长度最短的路径的宽度和，即 \(v\) 对 \(s\),\(t\) 的影响力。

一个人 \(v\) 在图中的传播力 \(R(v)\) 可以被定义为如下函数：

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

即对图中所有不包含 \(v\) 的点对，分别计算 \(v\) 对该点对的影响力除以该点对的最短路的宽度，再乘上这个点对中两个点的号召力，最后将所有点对的计算结果加和得到节点在图中的传播力。

B 君想快速知道所有节点在图中的传播力。当他去问小强的时候，小强说：“我有一个绝妙的做法，可惜题面太短，写不下。”

你知道怎么做吗？

输入

第一行，2个正整数 \(n,m\)，分别表示图的点数和边数。
接下来 \(n\) 行中的第 \(i\) 行有 \(1\) 个非负整数 \(a_i\)，表示第 \(i\) 个人的号召力。
接下来 \(m\) 行中的第 \(j\) 行有 \(3\) 个整数 \(x_j,y_j,b_j\) 和一个实数 \(c_j\)，表示点 \(x_j\) 和 点 \(y_j\) 之间有一条长度边权为 \(b_j\)，宽度边权为 \(c_j\) 的边。

输出

共 \(n\) 行，每行一个实数 \(R(i)\)，表示第 \(i\) 个点在图中的传播力。

样例 1

输入

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

提示

评分标准

我们会将输出文件的每个数与参考答案进行比较，如果该数与参考答案的相对误差或绝对误差不超过 \(10^{-6}\)，则判定该数正确。对于参考答案为 \(0\) 的数，必须满足绝对误差不超过 \(10^{-6}\) 才判定为正确。

如果输出正确数的个数为 \(q\)，那么你在该测试点上的得分是 \(\left\lfloor\ 5(\dfrac{q}{n})^7 \right\rfloor\)

数据范围限制

对于测试点 \(1,2,3,4\)，有 \(n \leq 100\)。
对于测试点 \(5,6,7,8\)，所有 \(b_j =1\)。
对于测试点 \(9,10,11,12\)，有 \(m=n-1\)。
对于测试点 \(1,3,5,7,9,11,13,15,17,19\)，所有\(a_i=1\)。
对于测试点 \(1,2,5,6,9,10,13,14,17,18\)，所有\(c_j=1\)。
对于所有的数据，有 \(n \leq 1000\),\(m \leq 4 \times 10^3\),\(0 < a_i < 255\),\(0 < b_j \leq 15\),\(0.5 < c_j \leq 2\)，\(c_j\) 的小数部分最多 \(12\) 位。数据保证图是连通的。

来源

CTSC2015