题目描述

有一个无向图，给定 $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$ 的最小代价。

输入输出样例 #1

输入 #1

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

输出 #1

8
3
14

输入输出样例 #2

输入 #2

4 5
1 2 1 7
3 1 3 2
2 4 5 2
2 3 1 1
2 4 7 1

输出 #2

7
6
44

输入输出样例 #3

输入 #3

3 2
1 2 2 5
2 1 3 3

输出 #3

9
-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。