AT_abc414_g [ABC414G] AtCoder Express 4

In AtCoder Kingdom, there is a railway line extending east-west, and this line has stations $ 1,2,\ldots,N $ . Station $ i\ (1\leq i\leq N) $ is located at coordinate $ x_i $ $ (x_1 < x_2 < \ldots < x_N) $ . On this line, AtCoder Express company operates $ M $ types of express trains. The $ i $ -th type of express train operates as follows: - You can board this train at one of the stations $ l_i,l_i+1,\ldots,r_i $ . - You can get off this train at one of the stations $ L_i, L_i+1, \ldots, R_i $ . Here, the train travels in one direction, either east or west, satisfying $ r_i\lt L_i $ or $ R_i\lt l_i $ . - The fare consists of a base fare of $ c_i $ plus an amount based on the distance from the boarding station to the destination station. Specifically, when traveling from station $ s\ (l_i\leq s\leq r_i) $ to station $ t\ (L_i\leq t\leq R_i) $ , the fare is $ c_i+|x_s-x_t| $ . You are currently at station $ 1 $ . For each $ k\ (2\leq k\leq N) $ , determine whether you can travel from station $ 1 $ to station $ k $ by transferring between express trains, and if you can travel, find the minimum total fare required for the travel.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ x_1 $ $ x_2 $ $ \ldots $ $ x_N $ $ l_1 $ $ r_1 $ $ L_1 $ $ R_1 $ $ c_1 $ $ l_2 $ $ r_2 $ $ L_2 $ $ R_2 $ $ c_2 $ $ \vdots $ $ l_M $ $ r_M $ $ L_M $ $ R_M $ $ c_M $

Output the answer in the following format: > $ \mathrm{ans}_2 $ $ \mathrm{ans}_3 $ $ \ldots $ $ \mathrm{ans}_N $ $ \mathrm{ans}_i $ is the answer for $ k=i $ . If you can travel from station $ 1 $ to station $ i $ , $ \mathrm{ans}_i $ is the minimum total fare required for the travel; otherwise, $ \mathrm{ans}_i $ is `-1`.

### Sample Explanation 1 You can travel to station $ 2 $ as follows: 1. Board the $ 1 $ st express train at station $ 1 $ and get off at station $ 6 $ . The fare is $ c_1+|x_1-x_6|=100+|0-150|=250 $ . 2. Board the $ 3 $ rd express train at station $ 6 $ and get off at station $ 2 $ . The fare is $ c_3+|x_6-x_2|=30+|150-20|=160 $ . The total fare in this case is $ 410 $ , which is the minimum. You cannot travel to station $ 4 $ . ### Constraints - $ 2\leq N\leq 10^5 $ - $ 1\leq M\leq 10^5 $ - $ 0\leq x_1 < x_2 < \ldots < x_N \leq 10^{12} $ - $ 1\leq l_i\leq r_i\leq N, 1\leq L_i\leq R_i\leq N $ - $ r_i\lt L_i $ or $ R_i\lt l_i $ . - $ 1\leq c_i\leq 10^{12} $ - All input values are integers.