题目描述

给定一个包含$N$个点和$M$条边的有向图，每条边$(uᵢ, vᵢ)$有两个属性$(aᵢ, bᵢ)$。需要找到从节点$1$到节点$N$的所有路径中，路径权值（路径上所有边的$a$之和与$b$之和的乘积）最小的路径。若有多个路径权值相同，选择$a$之和最小的路径。

输入格式

第一行输入$N$和$M$，分别表示图的点数和边数。

接下来$M$行，每行四个整数$uᵢ, vᵢ, aᵢ, bᵢ$，表示一条有向边的起点、终点及其权值属性。

输出格式：

输出一行，包含两个整数，分别为最小权值路径对应的$a$之和和$b$之和。

样例

样例输入

5 9
3 4 3 5
4 5 5 1
1 4 2 2
3 4 5 2
1 4 2 4
2 1 3 2
4 2 5 4
4 1 2 2
4 1 3 1

样例输出

7 3

数据分布

$40\%$的数据，$1 \le N \le 10$,$1 \le M \le 100$,$1 \le a_i,b_i le 10$

$100\%$的数据，$1 \le N \le 300$,$1 \le M \le 1000$,$1 \le a_i,b_i le 200$

数据保证保证一定存在从1到N的路径。

时空限制

• 时间限制：$1s$
• 空间限制：$256M$