###name explorer

###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 .

###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.

###sample input 5 5 1 2 1 4 2 3 1 2 3 5 2 4 2 4 1 3 4 5 3 4

###sample output 2

###hint There are 2 valid sizes : 2 and 3. For size 2, there exists a path 1→2→3→5. For size 3, there exists a path 1→2→4→5.

###toturial 把l,r看作限制，从小到大枚举区间，则表现为删边加边，然后问图的联通情况。这可以用直接lct维护。

###code

-----------------------本文结束感谢您的阅读-----------------------