Mirko 和 Slavko 是 Dabrovina Donja 大奖赛的仅有的两名参赛者，比赛在附近的村庄之间进行。村庄之间通过单向道路连接，对于每条道路 $i$，我们已知 $M_i$ 和 $S_i$，分别代表 Mirko 和 Slavko 通过该道路所需的时间。比赛路线本身是环形的（即起点和终点在同一个村庄），但具体的路线尚未确定。

Mirko 贿赂了比赛的组织者，让他们选择一条对他有利的路线。具体来说，组织者将选择一条最短路线（包含最少数量的道路），使得 Mirko 在该路线上严格快于 Slavko。如果碰巧有几条这样的路线，组织者会选择 Mirko 获得最大优势的那条。

输入格式

输入的第一行包含两个整数 $N, M$（$2 \le N \le 300$，$2 \le M \le N(N-1)$），分别表示村庄的数量和连接道路的数量。

接下来的 $M$ 行，每行包含 4 个整数 $A_i, B_i, M_i, S_i$（$1 \le A_i, B_i \le N$，$A_i \neq B_i$，$0 \le S_i, M_i \le 10^6$）。分别表示第 $i$ 条道路的起点村庄、终点村庄、Mirko 通过该道路所需的时间以及 Slavko 通过该道路所需的时间。

不存在两条连接相同村庄对且方向相同的不同道路。

输出格式

输出的第一行也是唯一一行应包含两个整数：使得 Mirko 获胜的最短可能路线（包含最少数量的道路）的道路数，以及在具有该最短长度的路线中，Mirko 所能获得的最大优势。

说明

请注意：输入数据保证总是存在一条满足上述条件的路线。

样例

输入样例 1

3 4 
1 2 3 0 
2 3 3 0 
3 1 0 100 
2 1 0 4

输出样例 1

2 1

输入样例 2

5 7 
1 2 4 1 
2 3 5 1 
3 1 1 6 
1 3 15 5 
2 4 7 5 
4 5 1 4 
5 3 1 0

输出样例 2

5 2