檀香梅

blossom .cpp/.in/.out

2s 128mb

题目背景

冬柏相当喜欢烟花。

这是一种娱乐活动，火药升上天空，然后爆开。

我们中的一些人嘲弄她有一项激进的爱好。

还有一些人开玩笑说她可能会在以后的朗术会上展示一个炸弹。

当然，我们都没有恶意。

然而……冬柏所渴望看到的是更为遥远的东西。

就像我们所做的那样。

她希望看到星星在天空中流淌，花朵在大地上绽放。

就是这样。

现在，过去的九人会联盟已经分崩离析。

当我窥视她的一生时，我目睹了一场世界因科技而支离破碎的悲剧。

她一定很倍感愤懑。

那一定是渴望、痛苦、悲哀而又绝望的。

正如我一样。

冬柏的所有情感，终于冲破了她的肉体，绽放出散乱的花瓣。

啊。你终于停下来了么，冬柏？

直到创造了一个没有技术残留的理想废墟之后……

把我们灿烂的故乡盛放在自己的身上。

我懂了，我明白了。

你之所以绽放并播下憧憬的花种，是为了祝愿我们有一个崭新的开始。

冬柏……随着花蕾再次绽放，你曾经所喜爱的烟火表演也再度重现在这片大地。

……的确，难怪你会对它们情有独钟。

题面

春风烂漫，绽放ego::檀香梅 东柏的身边此时有很多片山茶花海，一共有 $n$ 片山茶花海，第 $i$ 片山茶花海位于坐标 $x_i,y_i$，同时，一共有 $m$ 个镜子，若你在山茶花海 $i$ 内，你有以下两个选择

1. 选择另一片山茶花海 $j$，若 $x_j≥x_i$ 且 $y_j≥y_i$，则你可以花费 $y_j-y_i$ 的代价乘着刹那花风从山茶花海 $i$ 来到山茶花海 $j$

2. 如果山茶花海 $i$ 下有一个通向山茶花海 $j$ 的权值为 $w$ 的镜子，则你可以花费 $w$ 的代价传送到山茶花海 $j$ 旁，此处注意，镜子是单向的

现在你在山茶花海 $1$，请对于每一片山茶花海 $i(1≤i≤n)$，请找到一条路径从山茶花海 $1$ 通向山茶花海 $i$ 且花费的代价最小

输入

第一行输入两个数 $n,m$

接下来 $n$ 行，输入 $2$ 个数 $x,y$

接下来 $m$ 行，输入 $2$ 个数 $u,v,w$，表示 $u$ 到 $v$ 之间有一个权值为 $w$ 的镜子

为了不麻烦各位，保证 $x_i\leq x_{i+1}$ 且当 $x_i = x_{i+1}$ 时有 $y_i≤y_{i+1}$

输出

输出 $n$ 个整数，中间用空格连接，第 $i$ 个整数表示从山茶花海 $1$ 到山茶花海 $i$ 所需要花费的最小代价，若无法到达山茶花海 $i$，则输出 $-1$

样例

3 1
1 1
3 3
5 0
1 2 1

0 1 -1

6 6
1 19
2 56
3 51
4 108
5 95
6 126
1 5 0
6 1 0
4 2 1
2 5 0
6 3 1
5 3 0

0 37 0 57 0 31 

数据范围 && 约定

$1≤n≤5\times 10^4,0≤m≤30,1≤x_i,y_i≤10^8,1≤u_i,v_i≤n,0\leq w_i≤10^8$

保证输入的所有数据都是整数，保证出题人不玩原神，保证lzx玩原神（$57$ 级，快去膜拜%%%）