In the city of Hamirpur, there are three means of transport, feet, bus and rickshaw. You are given a map of the city with N places of interest and the description of roads between these places of interest. There are different costs of traveling via each means of transport on each of these roads. However, you can only take a rickshaw at most once and a bus at most twice. You are in a hurry so you wish to make sure that you take the fastest path to reach from your home to the college. Find the cost of the shortest path, while satisfying these constraints.

Your home is node 1 and the college is node N

Input

First line contains the number of places N and the number of roads between these places M.

Then M lines follow, each of them describing a road.

Each road is described by 5 integers, u , v, $feet_i$, $bus_i$, $rickshaw_i$. The road is bidirectional road from u to v, with $feet_i$ time required to travel on feet, $bus_i$ is the time required to travel via bus and $rickshaw_i$ is the time required to travel via rickshaw.

Output:

Print the minimum time required to reach your college from home. If it is not possible to reach the college, print 1.

Constraints:

$1 <= N <= 7000$

$1 <= M <= min(N * (N - 1) / 2, 80000)$

All times are less than or equal to $10^9$