You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定二维平面上有 $N$ 个点。第 $i$ 个点位于 $(X_i, Y_i)$。它们之间有 $M$ 条双向隧道。第 $j$ 条双向隧道连接 $U_j$ 和 $V_j$ 两点，从隧道的一端移动到另一端需要 $W_j$ 个单位时间。

旅行家有两种旅行方式：通过隧道，或是传送。旅行家可以用 $\min(|X_i - X_j|, |Y_i - Y_j|)$ 单位的时间从点 $i$ 传送到点 $j$。在这里，$|x|$ 表示 $x$ 的绝对值。

请你找出从点 $1$ 旅行到所有其他点的最短时间。

输入格式

从 teleport.in 文件读入数据。

第一行输入包含两个整数：$N, M$。

接下来的 $N$ 行中，第 $i$ 行包含两个整数：$X_i, Y_i$，描述第 $i$ 个点。

接下来的 $M$ 行中，第 $j$ 行包含三个整数：$U_j, V_j, W_j$，描述第 $j$ 条双向隧道。

输出格式

输出到 teleport.out 文件。

输出一行 $N - 1$ 个整数，其中第 $i$ 个整数是从点 $1$ 旅行到点 $i + 1$ 所需的最短时间。

样例

5 4
1 1
4 6
3 4
4 3
6 6
1 2 2
1 3 1
3 4 1
4 5 5

2 1 2 2

样例 2

点击链接 ex_teleport2.in 和 ex_teleport2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于所有测试数据，

$2 \leq N \leq 2 \times 10^5$，

$0 \leq M \leq 2 \times 10^5$，

对于所有 $1 \leq i \leq N$，$1 \leq X_i, Y_i \leq 10^9$，

对于所有 $i \neq j$，$(X_i, Y_i) \neq (X_j, Y_j)$，

对于所有 $1 \leq j \leq M$，$1 \leq U_j \neq V_j \leq N$

对于所有 $1 \leq j \leq M$，$1 \leq W_j \leq 10^9$。