题目描述
有一个无向图，给定 $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
4 4
1 2 2 4
3 4 4 1
4 2 1 1
1 3 3 1
样例输入 #2
4 5
1 2 1 7
3 1 3 2
2 4 5 2
2 3 1 1
2 4 7 1
样例输入 #3
3 2
1 2 2 5
2 1 3 3
提示
对于 $100\%$ 的数据，满足 $1 \le n,m,T_i,C_i \le 2000,1 \le A_i,B_i \le n$。