该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

在这里，你将扮演一位经验丰富的冒险家去寻找失落的宝藏

题目

在地图中有多个传送装置，每个传送装置都有一个配对值，当配对值相等时两个传送装置之间就可以互相传送， 地图的起始点位于左上角，现在你要去到右下角开启宝藏，因为你的体力并不支持你一直探索，所以你要在出发前寻找到最省时省力的方式。(ps:传送和移动都会消耗1点体力且在传送装置上可以选择不传送,你只能选择向地图上当前点的上下左右四个方向进行移动）

输入

第一行输入两个数 $1 \leq n,m \leq 1e4$ 接下来 $n$ 行 每行 $m$ 个字符 . 字符 '0' 表示不能走 '1' 表示能走 然后一个字符 $0\leq k \leq min(n*m,500)$ 表示传送装置的个数 接下来 $k$ 行每行三个整数 $x,y,z$ 表示传送装置在第 $x$ 行第 $y$ 列，配对值为 $z$ 保证$x,y$合法且不会出现传送装置在'0'上的情况

输出

如果能到达，输出体力消耗的最小值，如果不能到达，输出"No! It's impossible!"

样例

5 5
11111
00000
11111
00000
11111
4
1 5 1
3 1 1
3 5 2
5 1 2

14

5 5
11111
00000
11111
00000
11111
3
1 5 1
3 1 1
3 5 2

No! It's impossible!

限制

保证$n*m\leq1e6$

$0\leq z \leq 105$

1s, 1024KiB for each test case.