← 返回题目列表

AtCoder · abc022_c

C. 蓝鸟

中文机器翻译题面 查看原题

問題文

高桥君居住的小镇 N 个体房屋和 有 M 路径。 房子是 以 1 ~ N 整数编号。 高桥到家了 我住在 1 。 路也 以 1 ~ M 整数编号。 i 第三条路是家 u_i 和房子 两个方向连接 v_i 的长度 l_i 这是一米路。

高桥正在寻找“蓝色幸福鸟”,据说它在城市某处的一所房子里。 事实上,‘青幸福鸟’就在高桥家,高桥也知道这件事。 但是,如果不去旅行寻找一些东西,哪怕只是形式,也会很无聊,也没什么意思,所以我只好开始计划旅行。

高桥计划计划一次旅行,从他家开始,参观几所房子,以免多次走同一条路线,最后回到他家。 为了在这个时候制造兴奋感,至少在旅途中参观一下除了你自己的房子之外的房子。 1 我打算去看房子。 高桥想尽快结束这场闹剧,所以他认为最好的方案是尽量减少路径的总长度。

给定高桥所居住的城镇的房屋和道路信息,找出高桥能否在上述条件下制定出最优方案。 如果您可以制定最佳计划,请找出您将采取的路径的总长度。


入力

输入是从标准输入按以下格式给出的

N M
u_1 v_1 l_1
u_2 v_2 l_2
:
u_M v_M l_M
  • 1 第一行显示的是高桥所居住的城镇的房屋数量。 N(3 ≦ N ≦ 300) 和道路数量 M(3 ≦ M ≦ N(N-1)/2) 用空格分隔。
  • 2 从线 M 行 i 在线 i 第条路所连接的门牌号 u_i, v_i(1 ≦ u_i < v_i ≦ N) 和一个表示其长度的整数 l_i(1 ≦ l_i ≦ 10^5) 用空格分隔。
  • i ≠ j 如果 u_i ≠ u_j 或 至少 v_i ≠ v_j 之一成立。

出力

如果您无法制定最佳计划 -1 ,如果可能的话,计算当时所走路径的总长度。 在 1 行输出。还在输出末尾添加换行符。


入力例1

5 7
1 2 2
1 4 1
2 3 7
1 5 12
3 5 2
2 5 3
3 4 5

出力例1

13

房子和道路看起来像这样: 最好的计划是按以下顺序访问它们:

1, 2, 5, 3, 4, 1 。 计划访问顺序为 1, 2, 1 是 1 第路径 由于已通过 2 次,因此不满足条件。


入力例2

5 4
1 2 1
1 3 1
1 4 1
1 5 1

出力例2

-1

相同的路径 2 您无法计划一次不会多次进行的旅行。因此 输出 -1 。


入力例3

10 12
1 4 3
1 9 1
2 5 4
2 6 1
3 7 5
3 10 9
4 7 2
5 6 6
5 8 5
6 8 3
7 9 5
8 10 8

出力例3

11