Description

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$。

Format

Input

每组输入包含多组测试数据。第一行包含测试数据的组数 $T$（$1 \leq T \leq 12$）。接下来是各组测试数据的描述。

每组测试数据的第一行包含两个整数 $n, m$（$2 \leq n \leq 10^5$，$1 \leq m \leq 3 \times 10^5$），分别表示节点的数量和边的数量。

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

Output

对于每组测试数据，输出一行，包含 $\min_e$ 和 $\max_p$，中间用一个空格分隔。

保证答案一定存在！！！

Samples

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

2 2
1 0

Source

Super League of Chinese College Students Algorithm Design 2022, Contest 4 (BIT round)