P13901 [CSPro 28] 星际网络

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。

23333 年，在经过长时间的建设后，一个庞大的星际网络终于初具规模。星际网络共接入了 $n$ 颗星球，由 $m$ 颗中继卫星来实现星球之间的互联互通。所有星球之间的通信都必须经由一颗或多颗中继卫星来实现，星球本身也可以起到中继的作用，如果两颗星球的距离很远，数据可以沿“星球——中继卫星——星球——中继卫星——...——星球”的模式进行传输。 对于每一颗中继卫星而言，可以与多颗距离上较为接近的星球通信，但由于卫星结构的设计原因，通信只能单向进行。具体而言，第 $i$ 颗中继卫星可以接收编号在 $[l_{1i}, r_{1i}]$ 范围内的星球发送来的数据，并向编号在 $[l_{2i}, r_{2i}]$ 范围内的星球发送数据。 数据在星际之间传输的延迟当然是惊人的。为简单起见，我们假设这一延迟只由数据经过的中继卫星决定，即数据从不同的星球发出，经同一个中继卫星，到达不同的星球，所需的延迟时间总是相同的。对于第 $i$ 颗中继卫星，数据经由该中继卫星传输所需的延迟时间约为 $T_i$ 秒。由于这个数字实在太过巨大，而且对于星际间通信的延迟估计总是充满了各种不准确因素，我们只关心其若干位有效数字，具体而言将给出二元组 $(a_i, b_i)$，表示 $T_i = a_i \times 2^{b_i}$。我们假设数据在其他位置的延迟均可忽略。实际传输中，数据从源星球发出，经由很多颗中继卫星和星球最终到达目的星球，则总延迟为过程中经过的所有中继卫星的延迟之和。 数据从某个星球出发到达另一个星球，其在中继卫星和星球之间所经过的传输路径可能是多种多样的。与普通的计算机网络类似，我们需要设计相应的路由算法来选择合适的传输路径。一种直观的方案是最小延迟原则，即数据总是会选择总延迟时间最小的传输路径。 星际网络建成后，工程师们希望通过类似于计算机网络中 ping 的方法来测试该网络。从星球 A 向星球 B 发起一次 ping 的经过如下：首先从星球 A 发送请求数据，数据经星际网络传输至星球 B，星球 B 随即发送回复数据，经星际网络传输至星球 A，星球 A 计算从它发出请求到收到回复的所经时间，称为此次 ping 的响应时间。如果星际网络结构有缺陷，使得星球 A 发出的请求无法到达星球 B，或星球B发出的回复无法到达星球 A，则星球 A 在等待足够长时间后会得到“请求超时”的结果。 现在需要从 1 号星球向其他所有星球依次发起一次 ping，假设所有数据的传输均遵循最小延迟原则，请你计算出每次 ping 的响应时间。

从标准输入读入数据。 输入的第一行包含两个正整数 $n, m$。 接下来 $m$ 行：每行包含 6 个非负整数 $l_{1i}, r_{1i}, l_{2i}, r_{2i}, a_i, b_i$，描述一颗中继卫星，具体含义如上所述。

输出到标准输出。 输出一行包含 $n - 1$ 个整数，第 $i$ 个整数表示星球 1 向星球 $i + 1$ 发起 ping 的响应时间，答案对 $10^9 + 7$ 取模后输出。 特别地，如果某次 ping 的结果为请求超时，请输出 -1。

### 样例 1 解释 从 1 号星球到 2 号星球的请求数据最小延迟为 $4$，2 号星球的回复数据最小延迟为 $3$。 从 1 号星球到 3 号星球的请求数据最小延迟为 $4$，3 号星球的回复数据最小延迟为 $2$。 从 1 号星球到 4 号星球的请求数据最小延迟为 $5$，4 号星球的回复数据最小延迟为 $1$。 从 1 号星球到 5 号星球的请求数据最小延迟为 $6$，5 号星球的回复数据无法到达 1 号星球。 ### 数据范围 对于所有数据保证：$n \leq 10^5, m \leq 10^5, 1 \leq l_{1i} \leq r_{1i} \leq n, 1 \leq l_{2i} \leq r_{2i} \leq n, 1 \leq a_i \leq 10^9, 0 \leq b_i \leq 10^5$。 ::cute-table{tuack} | 测试点编号 | $n \leq$ | $m \leq$ | $b_i \leq$ | 特殊性质 | | :-: | :-: | :-: | :-: | :-: | | $1$ | $10$ | $10$ | $0$ | 无 | | $2 \sim 3$ | $100$ | $100$ | ^ | ^ | | $4 \sim 5$ | $1000$ | $1000$ | ^ | ^ | | $6 \sim 8$ | $10^5$ | $10^5$ | ^ | $l_{1i} = r_{1i}, l_{2i} = r_{2i}$ | | $9 \sim 10$ | ^ | ^ | ^ | $l_{1i} = r_{1i}$ | | $11 \sim 13$ | ^ | ^ | ^ | 无 | | $14 \sim 15$ | $100$ | $100$ | $100$ | ^ | | $16 \sim 17$ | $1000$ | $1000$ | $1000$ | ^ | | $18 \sim 20$ | $10^5$ | $10^5$ | $10^5$ | $l_{1i} = r_{1i}, l_{2i} = r_{2i}$ | | $21 \sim 22$ | ^ | ^ | ^ | $l_{1i} = r_{1i}$ | | $23 \sim 25$ | ^ | ^ | ^ | 无 |