C 神秘合金 (medal)

题目描述

Time limit: 2 s Memory limit: 256 MB

在神秘的金属世界里，研究员小A发现了一种特殊的有向图结构的合金。这个合金由 $N$ 个微观粒子节点和 $M$ 条连接它们的微观通道边构成。对于第 $i$ 条微观通道边，存在两个特殊的属性值 $(a_i, b_i)$。

定义一条从编号为 $1$ 的核心粒子节点到编号为 $N$ 的目标粒子节点的有向路径 $P$，其独特的性能值为：

小A急切地想要知晓从核心粒子节点 $1$ 到达目标粒子节点 $N$ 的所有可能路径中，能使合金性能达到最优（即性能值最小）的路径。请你协助他计算出这条路径所对应的 $(\sum_{i\in P}a_i)$ 和 $(\sum_{i\in P}b_i)$ 的值。

如果存在多条路径具有相同的最小性能值，那么请输出其中 $(\sum_{i\in P}a_i)$ 更小的那条路径所对应的 $(\sum_{i\in P}a_i)$ 和 $(\sum_{i\in P}b_i)$ 的值。

输入格式

第一行输入两个整数 $N, M$ $(1\leq N\leq 500, 1\leq M\leq 10^3)$，分别标识合金中微观粒子的数量（即图的点数）和微观通道的数量（即边数）。 接下来的 $M$ 行，每行包含四个整数 $u_i, v_i, a_i, b_i$ $(1\leq u_i, v_i\leq N, u_i\neq v_i, 1\leq a_i, b_i\leq 200)$，依次表示微观通道边连接的起始微观粒子节点、终止微观粒子节点以及该边所对应的两个特殊属性值。 保证在数据中至少存在一条从 $1$ 号微观粒子节点到 $N$ 号微观粒子节点的路径。

输出格式

输出能使合金性能最优的路径所对应的 $\sum_{i\in P}a_i$ 和 $\sum_{i\in P}b_i$ 的值。

样例

样例输入 1

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

样例输出 1

7 3

样例输入 2

5 14
1 2 90 44
2 3 132 73
3 4 116 124
4 5 160 93
4 2 61 30
5 4 196 136
1 4 126 116
4 3 184 55
2 1 20 181
3 2 83 112
1 5 97 126
5 1 2 131
4 1 66 111
2 4 193 183

样例输出 2

97 126

数据范围与约定

对于 $100\%$ 的数据，满足：

• $1\leq N\leq 500, 1\leq M\leq 10^3$
• $1\leq u_i, v_i\leq N, u_i\neq v_i, 1\leq a_i, b_i\leq 200$