P4524 [COCI 2017/2018 #4] Ceste

**原题时限2.5s**

有一个无向图，给定 $n$ 个顶点和 $m$ 条边，第 $i$ 条边连接 $A_i$ 和 $B_i$ 两个点且有两个代价 $T_i$ 和 $C_i$。 从第 $i$ 个顶点经过一些边到第 $j$ 个顶点花费的代价为这些边的 $T$ 之和乘以 $C$ 之和。 问题是，对于每一个 $k(2 \le k \le n)$，求从1号点出发到 $k$ 号点花费的最小代价。

第一行两个整数 $n$ 和 $m$。 接下来 $m$ 行，每行包含4个正整数 $A_i,B_i,T_i,C_i$，表示一条连接 $A_i,B_i$ 的路,代价为 $T_i,C_i$。

输出 $n-1$ 行，每行一个正整数，第 $i$ 行的正整数表示从城市1到城市 $i+1$ 的最小代价。

对于 $40\%$ 的数据，满足 $1 \le n,m,T_i,C_i \le 100$。 对于 $100\%$ 的数据，满足 $1 \le n,m,T_i,C_i \le 2000,1 \le A_i,B_i \le n$。 可能存在重边，不存在自环。 样例2解释： 为了到达城市2，我们选择第一条道路，花费1T与7C，代价为7。 为了到达城市3，我们选择第二条道路，花费3T与2C，代价为6。 为了到达城市4，我们选择道路2，4，5，花费11T与4C，代价为44。 2025/10/31 增加 hack 数据一组