【题目描述】

ST市一共有N个商贸中心，商贸中心之间通过M条双向道路相连（任两个商贸中心之间最多只有一条道路）

dd_engi打算在这N个商贸中心中挑选一个作为主店A，同时，为了扩大影响，dd_engi还打算再开一个分店B

主店和分点之间要经常的运送货物，为此dd_engi打算设计两条路线，一条从A到B，另一条从B到A

为了不会造成混乱，这两条路线除了起点和终点外不能经过同一个商贸中心

另dd_engi烦恼的是，每条道路的中点都设有一个收费站，不同道路的收费是不同的

如何选择A、B的位置才能使得两条路线的总费用最小呢？

为此dd_engi打算请你来帮他解决这个问题。

 

 

【输入】(transport.in)

第一行有两个数N，M

接下来的M行，每行有三个数A，B，C，表示AB之间有一条收费为C的双向道路

 

 

【输出】(transport.out)

输出只有一行，表示最小的费用

如果不存在解，则输出-1

 

 

【输入样例】

6 7

1 2 1

2 4 2

4 6 3

5 6 4

3 5 5

3 4 2

1 3 6

 

 

 

【输出样例】

11

 

 

【数据规模】

对于30%的数据，N≤30

对于60%的数据，N≤100

对于100%的数据，N≤400，C≤100000

上一篇文章：ping的高级用法

下一篇文章：OIBH的NOIP模拟试题