2413: 最佳运输

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

dd_engi打算在这N个商贸中心中挑选一个作为主店A，同时，为了扩大影响，dd_engi还打算再开一个分店B，主店和分点之间要经常的运送货物，为此dd_engi打算设计两条路线，一条从A到B，另一条从B到A。

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

另dd_engi烦恼的是，每条道路的中点都设有一个收费站，不同道路的收费是不同的，如何选择A、B的位置才能使得两条路线的总费用最小呢？

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

第一行有两个数N，M

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

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

如果不存在解，则输出-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