I : Python

Progress Bar

时间限制:1 Sec 内存限制:64 MiB

提交


题目描述

我们知道,在某些堕落腐朽的组织里,办理一些事情需要进行一些Python交易.

假如A要求通过B求C办事,则A要给B 元且耗费 点人情,B要给C 元且耗费 点人情。

当然,B的花费最终还是会由A来出,则A最终花费为 元和 点人情.

现在某个组织里面有N个成员,编号为1到N。

某个人想求另一个人办事,你能给出一个方案,使得他花费的钱最少吗?

如果两个方案花费的金钱相同,则选择花费人情更少的那个。

输入描述

第一行四个正整数n, m, s, e,分别代表组织的成员数,Python关系的数量,发起交易的人,达成交易的人。 接下来m行,每行4个正整数u, v, x, y。表示编号为u的成员可以花费x元和y点人情,到编号为v的成员那里达成Python交易,同一对成员之间可能存在多种Python关系。

输出描述

一行内输出两个正整数,分别代表花费的金钱和人情,以空格分割.

如果没有可行的方案,则输出"-1 -1".

样例输入

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

样例输出

11 13

来源

Wannacry-01