Description

聪聪是个非常单纯的小朋友。有一天他在食堂打饭的时候遇见了一位绝世MM，立刻就被吸引住了。

正当他想上前搭讪的时候，天空突然黑了，一个巨大的蚕宝宝从天而降，竟然把该MM吃了下去！蚕宝宝狂笑着对聪聪说：“这个MM，你给她东西吃，她就吃，你不给她吃，她自己就死掉了是吧？我已经把她藏到了我体内的最深处，再过不久她就饿死了！聪聪当然不会放过这个英雄救美的机会，于是他立刻施展法术，进入蚕宝宝体内去营救MM！

进入蚕宝宝体内后，聪聪发现蚕宝宝的身体是一个含有 N 个结点的有向图。聪聪所在的位置为 1 号结点，MM所在的位置为 N 号结点。两个结点之间可能会有多条路，通过每条路都需要一定的时间。另外，聪聪还发现这个迷宫中有一些隐藏的双向道路，通过隐藏道路不需要花费任何时间。当然，两个结点之间可能有不止一条隐藏道路。无论是普通道路还是隐藏道路，当聪聪第一次通过时能获得一定数量的金币。聪聪现在从 1 号结点出发，要到MM所在的 N 号结点。聪聪虽然救MM心切，但他也希望能多拿走一些金币，所以现在你的目标是：在保证所需时间最小的前提下，拿走最多的金币。

Format

Input

包含 M2 + M1 + 1 行。

第 1 行包含三个正整数 N、M1、M2，分别表示结点总数、普通道路与隐藏道路的数量。

第 2 行到 M2 + 1 行，每行包含三个正整数 A、B、C，表示有一条连接 A 和 B 的隐藏道路，该道路上的金币数为 C。

第 M2 + 2 行到 M2 + M1 + 1 行，每行包含四个正整数 A、B、C、D，表示有一条从 A 到 B 的普通道路，这条路上的金币数为 C，通过这条路所需花费的时间为 D。

Output

一行，依次输出最优方案所需的时间和金币数，中间用一个空格分开。

Samples

输入数据 1

4 4 1 
2 3 5 
1 2 8 2 
3 2 5 2
3 4 6 6 
1 4 10 9

输出数据 1

8 19

Explanation

最优路线为 1 → 2 → 3 → 4，其中 2 → 3 是隐藏道路。

Limitation

对于 10% 的数据，N ≤ 10，M1 ≤ 8，M2 = 0。

对于 30% 的数据，N ≤ 1000，M1 ≤ 50000，M2 = 0。

对于 50% 的数据，N ≤ 10000，M1 ≤ 200000，M2 = 0。

对于另外 30% 的数据，N ≤ 2000，M1 ≤ 60000，M2 ≤ 200。

对于 100% 的数据，N ≤ 10000，M1 ≤ 200000，M2 ≤ 1000。

通过每条普通道路所需的时间和通过每条道路所获得的金币数均不超过 100。

保证不会出现无解的情况，即至少存在一条从结点 1 通向结点 N 的路径。

my code： https://www.luogu.com.cn/paste/bev6rb39

（当然只有60pts，仅供参考，有Dj模版）

附问：

https://img.picui.cn/free/2025/06/15/684e59eddecf1.jpg

是什么东西？违规紫杉。