Problem
对于下一个暑期计算机学校，决定为学童和所有教师准备圆圈。
设计师有拖后腿的习惯，在开学前两天就完成了布局。制造商还需要一天的时间来制作杯子并在上面贴上图像。北约只需要24小时就可以将杯子从工厂运到LKSH。
10,000,000个马克杯的订单（也就是主办方订购的数量），当然不能一次带走。但是，对于第一次飞行，我想带上最大数量的杯子。订购了一辆重型卡车进行运输。但有一个警告：在某些道路上，汽车的重量是有限制的。所以，如果车上装满了眼珠子，那么走最短路线未必可以，反而要绕路。甚至可能会因此而导致卡车来不及准时到达营地，这是不能允许的。那么，为了有时间在不违反道路规则的情况下准时运送这些贵重货物，可以将多少个杯子装进车里？
输入
第一行包含数字 n (1≤n≤500) 和 m - 分别是道路图中的节点数和道路数。接下来的 m 行包含有关道路的信息。每条道路在单独的行中描述如下。首先，给出这条路连接的交叉点的数量，然后给出沿着这条路行驶所需的时间，最后给出允许在这条路上行驶的汽车的最大重量。已知所有道路都连接不同的点，并且对于每一对点，至多有一条道路直接连接它们。所有数字由一个或多个空格分隔。
节点从 1 到 n 编号。同时，生产杯子的工厂编号为 1，而 LKSH - 编号为 n。路上的旅行时间以分钟为单位，不超过 1440（24 小时）。质量限制以克为单位，不超过十亿。此外，众所周知，一个杯子重 100 克，而一辆空卡车 - 3吨。
输出
打印单数——首飞最多可携带的马克杯数量，停留时间不超过24小时。
例子
<头>
<日>#
| 输入 |
输出 |
<正文>
| 1 |
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
|
2 |