题目描述

Mirko 和 Slvako 参加了一次竞速比赛，这次比赛的地图有 $N$ 个村庄和 $M$ 条路。对于第 $i$ 条路有两个参数 $M_i$ 和 $S_i$，分别表示 Mirko 和 Slvako 通过这条路所需的时间。

比赛以同一个村庄为起点和终点。现在请你求出一条路线，使得 Mirko 通过这条路线所需的时间尽可能地优于 Slvako 通过这条路线所需的时间。

换句话说，令 $X$ 为 Mirko 通过路线所需的时间，$Y$ 为 Slvako 通过路线所需的时间，你需要求出一条路线，使这条路线通过的村庄数尽可能少的同时使 $Y-X$ 尽可能大。

输入格式

第一行，两个正整数 $N$ 和 $M$，表示共 $N$ 个村庄和 $M$ 条道路；

接下来 $M$ 行，每行四个正整数 $A_i,B_i,M_i,S_i$，分别表示第 $i$ 条道路连接村庄 $A_i$ 与 $B_i$，Mirko 通过这条路线所需的时间为 $M_i$，Slvako 通过这条路线所需的时间为 $S_i$。

输出格式

一行，两个正整数，分别表示所求道路通过的村庄数以及在这些通过村庄数最小的道路中使 $Y-X$ 最大的那条道路的 $Y-X$ 的值。

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

2 1

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 

5 2

提示

【数据范围】

对于 $100\%$ 的数据，$2\le A_i,B_i\le N\le 300$，$A_i\ne B_i$，$2\le M\le N\times (N-1)$，$0\le M_i,S_i\le 10^6$。

【来源】

本题分值按 COCI 原题设置，满分 $160$。

题目译自 COCI2013-2014 CONTEST #4 T6 UTRKA。