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

题目背景

魔多北部有一段山脉，被称为“灰烬山脉”

弗罗多想要穿过它，潜入魔多。

题目描述

山脉可以抽象成一个 $n$ 个点，$m$ 条边的图。由于索隆早已有所防备，因此每条边都有卫士看守，对于第 $i$ 条边，只有在 $[0,a_i)$，$[b_i,b_i+a_i)$，$[2 \times b_i,2 \times b_i+a_i)$ $\dots$ $[x \times b_i,x \times b_i+a_i)$ ($x$ 为正整数)，这些时间正好可以趁卫士交接班时潜入，通行的时间花费为 $c_i$。注意卫士看守的只有边的两头，只要弗罗多在卫士看不到的时候进入了边内部，那么即使他行走过程或者在出去时中有卫士监视，他也无法被看到。

现在要从 1 出发，求弗罗多最少需要花多少的时间才能到达 $n$。为了等待通过，弗罗多可以呆在一个节点任意长的时间。

输入格式

第一行两个数 $n$，$m$

接下来 $m$ 行，每行两个整数 $x_i$，$y_i$。表示第 $i$ 条边连接 $x_i$ 和 $y_i$。

在接下来 $m$ 行，每行三个正整数 $a_i$，$b_i$，$c_i$ 。

输出格式

输出答案。如果无解，输出 -1

提示

对于 20% 的数据，$n,m \leq 10$

对于 40% 的数据，$n \leq 100$

对于 60% 的数据，$n \leq 2000$

另外 5% 的数据，保证是一棵树

另外 5% 的数据，保证 $a_i$ 等于 $b_i$

对于 100% 的数据，保证 $n \leq 10^5$，$m \leq 7 \times 10^5$，$1 \leq a_i \leq b_i,c_i \leq 10^9$

/*

5 7

1 2

2 3

3 4

4 5

2 4

4 5

2 5

1 2 1

1 3 1000

2 5 100

1 10 99

1 2 1

1 2 1

1 100 100000

*/