AT_wupc2012_5.会場への道

题目背景

终于到了比赛的前一天了。为了比赛当天而早做准备，我将找好去比赛会场的路。从我住的小镇到比赛会场所在的镇（早稻田），会经过一些其它的小镇。小镇之间有一些道路连接。如果两个小镇间没有道路连接则不能在这两个小镇间移动。

无论如何我也想在比赛中取得胜利，所以我想保证一定能取胜。我相信能被 $4$ 或 $7$ 整除的数是能够给我带来好运的数。假设出发时的时间为 $0$ ，而到达会场的时间能够被 $4$ 或 $7$ 整除的话我的心情就会很好。然而，如果到达会场的时间不能被 $4$ 或 $7$ 整除，我就会觉得这次比赛肯定会输。为了在比赛中取得胜利，即使绕很远的路我也要在能被 $4$ 或 $7$ 整除的时间点到达会场。

去会场的移动方法很自由。曾经过的道路再次经过，回到已经去过的小镇或出发的小镇，都是允许的。但是，在一条道路的途中不能折返，在已经到达会场后不能再继续移动。

现在，请求出按满足以上条件的方式移动时，到达会场所用的最短时间。

给出连接 $N$ 个小镇的 $M$ 条道路的情况。每条道路连接不同的两个小镇。在指定时间内可以经由此路双方向移动。我所在的小镇的编号为 $0$ ，会场所在镇的编号为 $N-1$ （小镇的编号分别从 $0$ 到 $N-1$ ），另外出发时的时间为 $0$ 。请编写程序求出：按照到达会场所在小镇的时间能被 $4$ 或 $7$ 整除的方式移动时，最小的到达时间。不过，已经到达过会场便不能再移动。另外，在一条道路的途中不能折返或休息。

输入按以下形式：

$$N \space M$$

$$f_1 \space t_1 \space c_1$$

$$...$$

$$f_m \space t_m \space c_m$$

• 第一行为以空格隔开的两个整数 $N(2 \le N \le 1000)$ 和 $M(1 \le M \le min(10000,N×(N-1)/2))$ ，分别表示表示小镇数与道路数。
• 第二行到第 $M+1$ 行为各条道路的情况，也就是：该道路所连接的两个小镇的编号 $f_i$ 和 $t_i$ ，和从该道路一端移动到另一端所花时间 $c_i$ 。
• 对于任意 $i$ ，满足 $0 \leq f_i \leq N-1$ 且 $ 0 \leq t_i \leq N-1 , f_i ≠ t_i , 1 \leq c_i \leq 100000 $ 。
• 数据保证不会有重边和自环。可能会出现没有任何道路连接的小镇。

输出一行：按满足条件的方法移动到会场所花的最小时间。
数据保证一定有解。

部分分

对于 $30\%$ 的数据：在以上条件的基础上，保证能够在 $500$ 单位时间内到达会场。

输入输出样例

输入样例1

2 1
0 1 4

输出样例1

4

样例解释1

• 从出发的小镇到目标小镇需要的时间为 $4$ 。合计时间 $4$ 为 $4$ 的倍数，因此满足条件。故答案为 $4$ 。

输入样例2

3 2
0 1 15
1 2 5

输出样例2

20

样例解释2

• 从出发的小镇 $0$ 开始，花费 $15$ 单位时间到达小镇 $1$ ，从小镇 $1$ 花费 $5$ 单位时间移动到目标小镇 $2$ 。合计时间 $20$ 是 $4$ 的倍数。故满足条件，答案为 $20$ 。

输入样例3

4 3
0 1 1
1 2 1
2 3 1

输出样例3

7

样例解释3

• 从出发的小镇 $0$ 花费 $1$ 单位时间到达小镇 $1$ ，从小镇 $1$ 花费 $1$ 单位时间到达小镇 $2$ ，从小镇 $2$ 花费 $1$ 单位时间到达目标小镇 $3$ 。到达的时间为 $3$ ，而 $3$ 既不是 $4$ 的倍数也不是 $7$ 的倍数。故我们可以在小镇 $1$ 和小镇 $2$ 间反复移动，最后的总时间为 $7$ 。 $7$ 是 $7$ 的倍数。故满足条件，答案为 $7$ 。