Description

There are $n$ stations in Chongqing City, and $m$ bidirectional roads connect some of them. Between any two stations, there is at most one road. Starting from any station, you can reach any other station by taking one or more roads, but different paths may take different amounts of time. The time spent on a path equals the sum of the times of all roads on that path.

Jiajia’s home is at station $1$. He has five relatives who live at stations $a,b,c,d,e$. During the Spring Festival, he needs to start from home and visit each relative (in any order) to send them holiday greetings. How should he travel to spend the least total time?

Input Format

The first line contains $n,m$, the number of stations and the number of roads.

The second line contains $a,b,c,d,e$, the station numbers where the five relatives live.

The next $m$ lines each contain three integers $x,y,t$, representing the two stations connected by a road and the time of that road.

Output Format

Output only one line containing an integer $T$, the minimum total time. It is guaranteed that $T\le 10^9$.

6 6
2 3 4 5 6
1 2 8
2 3 3
3 4 4
4 5 5
5 6 2
1 6 7

21

Hint

For $40\%$ of the testdata, $1\le n\le 500$ and $1\le m\le 2000$.

For $100\%$ of the testdata, $1\le n\le 50000$, $1\le m\le 100000$, $1\le a,b,c,d,e\le n$, $1\le x,y\le n$, and $1\le t\le 10000$.

Translated by ChatGPT 5