U236666 【模板】线段树优化建图
题目描述
给定 $n$ 个点和 $m$ 对关系，求每个点到 $1$ 节点的最短路径的长度。如果不能到达则输出 `-1`。
$m$ 对关系包含两种关系：
`1 u v w`，表示 $u \rightarrow v$ 有一条长度为 $w$ 的有向边；
`2 u l r w`，表示 $u$ 向 $[l,r]$ 之间的每一个结点 $v_i$ 连一条长度为 $w$ 的有向边。
输入格式
第一行两个整数 $n,m$。
接下来 $m$ 行，每行表示一次操作。
输出格式
一行 $n$ 个整数，第 $i$ 个整数 $dis_i$ 表示 $1$ 到 $i$ 的最短路径的长度。
说明/提示
### 样例解释
样例 1 的图建立之后长这个样子：
$1$ 到各个点的最短路径长度显然分别是 $0,1,3,1$。
## 数据范围
对于 $100\%$ 的数据：
$1 \leq n \leq 10^5$，$1 \leq m \leq 2 \times 10^5$，$1 \leq u,v \leq n$，$1 \leq w \leq 10^9$。
**请注意代码的常数优化。**