Боб вирішив відправитися на канікули по містам Байтоляндії. В Байтоляндії є ~n~ міст, Боб живе в місті з номером 1. Щоб пересуватися по містам в Байтоляндії, після реформи запустили проїзні на потяги. Проїзний з номером ~i~ можна купити в містах з номерами від ~l_i~ до ~r_i~ включно за ~p_i~ гривень, і поїхати в будь-які міста з номерами від ~cl_i~ до ~rl_i~ включно. Якщо Боб вже купив проїзний, то він може скористатися ним безліч разів з будь якого міста. Боб ще не вирішив, в яке саме місто йому відправитися, тому просить вас для кожного міста сказати мінімальну суму, яку потрібно витратити, щоб дістатися до нього.

Input

Перший рядок містить числа ~n~ і ~k (1 \le n, k \le 10^5)~ - кількість міст в Байтоляндії та кількість проїзних.

Наступні ~k~ рядків містять по 5 чисел - ~l_i, r_i, cl_i, rl_i, p_i (1 \le l_i \le r_i \le n, 1 \le cl_i \le cr_i \le n, 1 \le p_i \le 10^9)~ - проміжок міст, в яких можна купити проїзний з номером ~i~ та проміжок міст, в які можна поїхати з цим проїзним і його ціна.

Output

Для кожного міста виведіть мінімальну суму, яку потрібно витратити Бобу, щоб потрапити туди. Якщо Боб не може поїхати в це місто, то виведіть -1.

Scoring

1) ~l_i~ = ~r_i~, ~cl_j~ = ~cr_j~, для всіх ~i, j~
2) ~k, n \le 100~
3) ~k, n \le 1000~
4) ~\sum (cr_i - cl_i + 1) \le 2*10^5~
5) ~l_i = r_i~
6) без обмежень

Sample Input 1

8 2
1 4 7 8 5
6 7 3 6 4

Sample Output 1

0 -1 9 9 9 9 5 5