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

There are nvertices 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.

###input The first line contains two positive integers n,m , denoting the number of vertices and roads. Following m lines each contains four positive integers u,v,l,r , denoting a bidirectional road (u,v,l,r) . $1≤n,m≤10^5 ,1≤u\lt v≤n,1≤l≤r≤10^9$

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