题目描述

徐老师最近很喜欢玩飞车游戏，最近游戏新出了双人对战模式

这张地图上有 $n$ 个检查点，检查点之间存在 $m$ 条车道

每条车道连通两个检查点 $u_i, v_i$，但是玩家只允许从编号小的检查点到达编号大的检查点

徐老师很想拉 wjr 入坑一起来玩这个游戏，所以热情的邀请 wjr 跟他一起来体验双人模式

但是徐老师和 wjr 的操作水平是不一样的，所以穿过每条车道所需要的时间也不同

对于第 $i$ 条车道，它连通 $u_i, v_i$ 两个检查点，徐老师通过这条车道需要的时间为 $A_i$, wjr 通过这条车道需要的时间为 $B_i$

为了照顾 wjr 的心情，徐老师决定为自己两人分别设计一条从 $1$ 号检查点到 $n$ 号检查点的路径，他希望两个人可以同时到达 $n$ 号检查点

现在徐老师想知道，在保证两人能同时到达 $n$ 号检查点的情况下，最少需要花费多少时间？

输入格式

输入第一行包含两个整数 $n,m$，含义如题

接下来 $m$ 行，每行包含四个整数 $u_i,v_i,A_i,B_i$，表示一条车道的信息

输出格式

输出仅一行，表示他们到达 $n$ 号检查点最少需要花费的时间，如果不存在两人能够同时到达的方案，则输出IMPOSSIBLE

Samples

3 3 
1 3 1 2 
1 2 1 2 
2 3 1 2

2

数据范围

对于 $20\%$ 的数据满足:$1 \leq n,A_i,B_i \leq 10$

对于 $40\%$ 的数据满足:$1 \leq n,A_i,B_i \leq 100, m \leq 2000$

对于 $100\%$ 的数据满足:$1 \leq n,A_i,B_i \leq 100, 1 \leq m \leq n * (n - 1) / 2, 1 \leq u_i,v_i \leq n$