题目描述

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

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

他们还有很多共同的好朋友，比如小花，葱娘和其他 $3$ 个人。

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

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

人与人之间的关系也各不相同，可能非常友好，可能只是泛泛之交；可能天天腻在一起，可能一年才联系一次。

为此，我们用长度边权 $b_j$ 来刻画第 $j$ 条边对应的两个用户的亲密程度，长度约小，双方就越亲密。

同时，我们用宽度边权 $c_j$ 来刻画第 $j$ 条边对应的两个用户的交流频率，宽度越大，两个人沟通的频率也就越高。

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

当两个人 $s$ 和 $t$ 想要交流的时候，他们会选择长度最短的路径来交流。由于最短路可能有多个，我们称 $s$ 到 $t$ 的最短路的宽度为 $\text{σst}$，是所有 $s$ 到 $t$ 的长度最短的路径的宽度和。

同时，我们用 $\text{σst(v)}$ 表示所有从 $s$ 到 $t$，且经过 $v$ 的长度最短的路径的宽度和，即 $v$ 对 $s,t$ 的影响力。

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

即对图中所有不包含 $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$ 行，每行一个实数 $\text{R(i)}$，表示第 $i$ 个点在图中的传播力，误差在 $10^{-6}$ 内。

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

数据规模与约定

对于测试点 $1 \sim 4$，$1 \le n \le 100$。

对于测试点 $5 \sim 7$，所有 $b_j = 1$。

对于测试点 $9 \sim 12$， $m = n-1$。

对于奇数测试点，所有 $a_i=1$。

对于偶数测试点，所有 $c_j=1$。

对于全部测试点，$1\le n,m \le 1000$，$0 < a_j \le 255$，$0 < b_j \le 15$，$0.5 \le c_j \le 2$，$c_j$ 的小数部分最多 $12$ 位，保证图连通。