题目背景

原题时限2.5s

题目描述

There’s a country with N cities and M bidirectional roads. Driving on road i takes $T_i$ minutes, and costs $C_i$ kunas (Croatian currency).

To make the arrival to the holiday destination as pleasant as possible, you want to make it as fast and as cheap as possible. More specifically, you are in city 1 and want to minimize the product of total money spent and total time spent (overall, with all roads you drove on) in getting to a city from city 1. For each city (except city 1), output the required minimal product or -1 if city 1 and that city aren’t connected.

输入格式

The first line of input contains numbers N (1 ≤ N ≤ 2000), the number of cities, and M (1 ≤ M ≤ 2000), the number of roads.

Each of the following M lines contains four numbers,$A_i,B_i,T_i,C_i,(1≤A_i,B_i≤N,1≤T_i,C_i≤2000)$ that denote there is a road connecting cities $A_i$ and $B_i$ , that it takes $T_i$ minutes to drive on it, and it costs $C_i$ kunas.

It is possible that multiple roads exist between two cities, but there will never be a road that connects a city with itself.

输出格式

You must output N - 1 lines. In the $i^{th}$ line, output the required minimal product in order to get to city (i + 1), or -1 if cities 1 and (i + 1) aren’t connected.

题目大意

题目描述：

有一个无向图，给定 $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。

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

8
3
14

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

7
6
44

3 2
1 2 2 5
2 1 3 3

9
-1

提示

In test cases worth 40% of total points, it will hold $1 ≤ N, M, T_i, C_i ≤ 100$.

Clarification of the second test case:

In order to get to city 2, you need to drive on road 1, for that it takes 1 minute and 7 kunas, so the required product is 7.

In order to get to city 3, you need to drive on road 2, for that it takes 3 minutes and 2 kunas, so the required product is 6.

In order to get to city 4, you need to drive on roads 2, 4, 5, in that order, and for that it takes a total of 11 minutes and 4 kunas, so the required product is 44.