SP1725 IMPORT1 - The Importance

给定一个无向带权图，由节点集 $V$ 和边集 $E$ 组成。你的任务是计算每个节点在图中的重要性。 节点 $v$ 的重要性 $I(v)$ 定义为： $$ I(v) = \sum_{s \neq v, t \neq v} \frac{C_{s,t}(v)}{C_{s,t}} $$ 其中，$C_{s,t}$ 表示节点 $s$ 到节点 $t$ 之间不同最短路径的数量，而 $C_{s,t}(v)$ 表示的是这些最短路径中经过节点 $v$ 的数量。

输入包含多组测试数据。第一行是测试数据的组数。 对于每组测试数据： 第一行包含两个整数 $n$ 和 $m$（$n \le 100$，$m \le 4500$），分别表示图中的节点数和边数。节点编号从 $1$ 到 $n$。接下来的 $m$ 行，每行包含三个整数 $a, b, c$（$1 \le a, b \le n$，$1 \le c \le 1000$，$a \neq b$），表示节点 $a$ 和节点 $b$ 之间存在一条权重为 $c$ 的无向边。假设每对节点之间最多只有一条边，并且任何两节点之间至少存在且至多存在 $10^{10}$ 条最短路径。

对于每组测试数据： 输出 $n$ 行，每行一个实数，保留三位小数。第 $i$ 行的实数表示第 $i$ 个节点的重要性。 **本翻译由 AI 自动生成**