問題文
高桥君居住的小镇 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