11老师当年代表四川省队参加NOI比赛的时候，认识了一个好朋友，叫做pear，虽然他们俩都拿到了当年的NOI金牌，但是没能一起读大学，因为pear出国了。 pear是一个火车迷，所以NOI考试结束后11老师和pear决定一起去坐火车旅游纪念这份信息学奥赛中相遇的缘分。 而你——我的学生，你需要穿越回10年前，为11老师和她的oi友情做出一个不错的规划。 11老师和pear制定了一个城市旅行计划，坐火车依次经过北京—石家庄—……—深圳，我们用编号1～n来表示。他们决定每次火车就坐一站直达，这样可以多体验几种旅途感受。 时空穿越回去的同学们知道所有的短途火车车次的发车时间、到达时间、出发点、目的地。 问在201410010000时刻后出发，最早要多久到达目的地。保证换乘等事宜不需要任何时间，上一趟车的到达时间可以和下一趟车的出发时间完全重合。

输入描述

从文件 travel.in 读入数据。 第一行2个整数，一个整数n表示城市的个数，一个整数m表示短途火车的车次情况。 第2～m+1行每行4个整数，表示本车次的发车时间、到达时间、出发点、目的地。 时刻用一个12位数字表示。

输出描述

输出到文件 travel.out。 输出最早到达的时刻，如果不存在合法路径则输出-1。

用例输入 1

3 5 201410010600 201410020800 1 2 201410010600 201410030000 1 3 201410010800 201410020000 1 2 201410020000 201410040000 2 3 201410030000 201410060000 2 3 用例输出 1

201410040000 提示

对于30%的数据，保证0<n,m<1000 对于100%的数据，保证0<n,m<100000,保证输入的时刻合法.