Link 讨厌跑步。

今天，Link 被要求去跑步。BIT 的道路可以描述为 $n$ 个节点和 $m$ 条有向边。Link 必须从节点 $1$ 跑到节点 $n$。当 Link 在节点 $u_i$ 时，他可以通过第 $i$ 条边到达节点 $v_i$。每次通过第 $i$ 条边时，他会消耗 $e_i$ 点能量并获得 $p_i$ 点体能。

作为一个懒孩子，Link 希望消耗尽可能少的能量。同时，他也很贪心，希望在消耗最少能量的前提下获得尽可能多的体能。

请告诉 Link 他需要消耗的最小能量 $min_e$，以及在消耗最小能量时他能获得的最大体能 $max_p$。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $T(1 \le T \le 12)$。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m(2 \le n \le 10^5, 1 \le m \le 3 \times 10^5)$，分别表示节点数和边数。

接下来的 $m$ 行，每行包含四个整数 $u_i, v_i, e_i, p_i(1 \le u_i, v_i \le n, 0 \le e_i, p_i \le 10^9)$，描述一条边。

输出格式

对于每个测试用例，输出 $min_e$ 和 $max_p$，中间用一个空格隔开。

题目保证答案一定存在！！！

样例

输入 1

2
3 3
1 2 1 1
2 3 1 1
1 3 2 0
3 3
1 2 1 1
2 3 1 1
1 3 1 0

输出 1

2 2
1 0