我绝对想在比赛中获胜。因此,为了万全起见,我要讲究吉利。我相信能被4或7整除的数是吉利的数。如果以出发时间为0,到达会场的时间能被4或7整除,我会感到心情愉快。但如果到达时的时间既不能被4也不能被7整除,我会觉得会在比赛中失败。为了在比赛中获胜,即使稍微绕路,也希望能在能被4或7整除的时间到达会场而移动。
去会场的移动方法是自由的。可以返回已经走过的道路,也可以回到已经经过的城市或我居住的城市。但是,不能在道路中途掉头,也不能在到达会场后再折返。
那么,当按照这个条件移动时,来试着求出到达会场所需的最短时间吧!
問題文
图1:输入例3中城市和道路的情况
入力
N M
f_{1} t_{1} c_{1}
...
f_{m} t_{m} c_{m}
- 1 行表示城市的数量 N(2 ≦ N ≦ 1000)与道路数量 M(1 ≦ M ≦ min(10000, N*(N-1)/2)) 由半角空格分隔。 您可以假设
- 2 行目~ M+1 每一行包含各条道路的信息,也就是道路连接的两个城市编号 f_{i} 和 按字典顺序比较 t_{i},以及移动所需时间 c_{i} 由半角空格分隔。 关于
- 各 i 关于 0 ≦ f_{i} ≦ N-1 和 0 ≦ t_{i} ≦ N-1 , f_{i} ≠ t_{i} , 1 ≦ c_{i} ≦ 100000 很满意。
- 连接两座城市的道路数量最多为 1 条。也可能存在城市没有任何道路连接的情况。
出力
另外,保证可以以满足条件的方式移动到会场。
部分点
入力例 1
2 1 0 1 4
出力例 1
4
- 可以从起点城市0以时间4到达终点城市1。总时间4是4的倍数,因此满足条件。所以答案是4。
入力例 2
3 2 0 1 15 1 2 5
出力例 2
20
- 你可以在15小时内从起始城市0到城镇1,从城市1到目标城镇2需要5小时。由于总时间20是4的倍数,它满足了条件。因此,答案是20。
入力例 3
4 3 0 1 1 1 2 1 2 3 1
出力例 3
7
- 你可以在时间1内从起始城镇0到城镇1,从城市1到城镇2,从城镇2到目标城镇3在1小时内。如果你沿着从起点到目标的最短路线走,总共需要3次,但既不是4,也不是7的倍数。如果你在城镇1和城市2之间来回两次,总时间是7,是7的倍数,所以满足条件。因此,答案是7。