Explorer

题号：NC51610
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Gromah and LZR have entered the fifth level. Unlike the first four levels, they should do some moves in this level.

There are $n_{}$ vertices and $m_{}$ bidirectional roads in this level, each road is in format $(u, v, l, r)_{}$ , which means that vertex $u_{}$ and $v_{}$ are connected by this road, but the sizes of passers should be in interval $[l, r]_{}$ . Since passers with small size are likely to be attacked by other animals and passers with large size may be blocked by some narrow roads.

Moreover, vertex $1_{}$ is the starting point and vertex $n_{}$ is the destination. Gromah and LZR should go from vertex $1_{}$ to vertex $n_{}$ to enter the next level.

At the beginning of their exploration, they may drink a magic potion to set their sizes to a fixed positive integer. They want to know the number of positive integer sizes that make it possible for them to go from $1_{}$ to $n_{}$ .

Please help them to find the number of valid sizes.

输入描述:

The first line contains two positive integers , denoting the number of vertices and roads.

Following m lines each contains four positive integers , denoting a bidirectional road .

输出描述:

Print a non-negative integer in a single line, denoting the number of valid sizes.

示例1

输入

复制

输出

复制

说明

There are 2 valid sizes : 2 and 3.

For size 2, there exists a path .

For size 3, there exists a path .