2011 年的那个时候,编程比赛还非常和平, 我们可以不仔细阅读规则就轻松参与比赛。 然而,G○○gle 的阴谋悄然逼近。 有一天,被 G○○gle 秘密收购的 T○pC○der 比赛, 规则在不知不觉中被更改,变成了生死攸关的编程比赛。 而我,在那里,毫不知情, 率先发现了 kita_masa 程序的溢出问题…。
- (毛利部落)
- “呜呜…啊…”
- 瓦塔
- “现在该做的不是责怪自己。你是想浪费这个机会吗?”
…说起来,现在这个家伙,一瞬间就击倒了房间里的所有人。 这是怎么回事?
- 瓦塔
- 「首先,你可能已经知道,G○○gle 拥有针对包括 NP 完全问题在内的许多被认为计算上困难的问题的多项式时间高效算法。它解决了 P vs NP 问题,但故意隐瞒了这一点,由此才发展到今天的规模。」
- (毛利部落)
- 「我早就有所怀疑,果然如此……但是,你刚才瞬间就击败了 G○○gle 的人。难道你也是……?」
- 瓦塔
- 「很遗憾,不是。不过……如果是你的话,应该明白吧?」
……原来如此!! 原来是这样。 他在大学时期,对将指数时间算法加速非常感兴趣。 即使是指数时间,如果指数的底数非常小, 对现实中的实例也可能足够快。
- 瓦塔
- 「就是这样的。例如,现在我正尝试完成旅行推销员问题的 O*(1.0001n) 时间算法。」
惊人,超出想象……。
- 瓦塔
- “为了完成它,我需要你在图算法方面的能力。能帮忙吗?”
- (毛利部落)
- “啊,当然可以。交给我吧!!”
問題
给定一个图。 图具有N 个顶点,每个顶点编号为 1 减去 N 。 此外,图有 M 条边,边是有向的(单行),每条边都有特定的距离。
頂点 1 从顶点出发,依次访问顶点 2, 3, …, N ,然后返回顶点 1 。 这里,“依次访问”是指路径中包含作为子序列的顶点 2, 3, …, N 。 换句话说,从起点顶点 1 到顶点 2 的移动,无论是直接移动还是经过其他顶点的移动,都是可以的,并且下一个顶点 2 到顶点 3的移动, 接着到下一个顶点 3 到顶点 4的移动等也同样适用。 同一个顶点或同一条边可以经过两次。
给定一个图时, 从顶点 1 出发,按此顺序访问顶点 2, 3, …, N ,再返回顶点 1 的路径中, 输出最短路径的长度。 路径的长度是路径中包含的边的距离之和。 对于多次包含的边,应按包含的次数累加距离。
入力
输入的第一行包含两个整数 N, M 。 这表示图的顶点数和边数。
继续 M 行表示边的信息。 这些行中的第 i 行包含三个整数 ai, bi, ci , 连接边 i 是顶点 是 ai 到顶点 bi ,其距离为 ci 。
出力
输出满足条件的路径中最短路径的长度。 但是,如果不存在满足条件的路径,请输出 -1。
制約
- 2 ≤ N ≤ 105
- 0 ≤ M ≤ N + 500
- 1 ≤ ai, bi ≤ N,ai ≠ bi
- 1 ≤ ci ≤ 103
入出力例
入出力例 1
入力例 1:
5 5 1 2 10 2 3 20 3 4 30 4 5 40 5 1 50
输入示例 1 的输出示例:
150
入出力例 2
入力例 2:
5 5 1 5 10 5 4 20 4 3 30 3 2 40 2 1 50
输入示例 2 的输出示例:
600