牛妹设计了一个进入牛牛国的游戏，用时最短到达的人就能陪牛妹一起过七夕,拜七姐，祈福许愿、乞求巧艺、坐看牵牛织女星、祈祷姻缘、储七夕水等七夕的传统习俗。
游戏的设定如下:
去往牛牛国只有一条长度为n的道路，你从0开始出发，初始时间为0，速度为1，路线上有m个挡板，挡板会站在路旁的阻止你前往牛牛国，不过你也不是没有通过的机会，每个挡板从0时刻在位置p在路中央开始工作，进入升起状态挡住行人a单位时间，随后降落状态行人可自由通过b单位时间的循环中。
第一行两个正整数n,m(1<=n<=1e9,m<n,1<=m<=1e5）。
接下来有m行，每行三个正整数表示每个挡板的初始位置p(0<p<n，数据保证挡板位置不重复)，升起状态持续的时间a，降落状态持续的时间b(1<=a,b<=1e5)。
输出一个正整数代表最短时间。