Dr. Henri has recently been studying wormholes, tunnels in the fabric of spacetime. A wormhole connects two different galaxies, may be traversed in either direction, and allows one to travel between the two galaxies in mere minutes. Wormholes are very rare and contain all sorts of exotic matter.
One day, Dr. Henri and his team discover a cluster of galaxies connected by wormholes! Wormhole connects galaxies and and takes minutes to traverse. Dr. Henri notes that it is possible to travel from any galaxy to any other galaxy in the cluster using wormholes.
As Dr. Henri and his team are very interested in exotic matter, they plan to dispatch a space probe into the galaxy cluster to investigate. They want to choose a path through the cluster so that the probe spends the longest time possible travelling through wormholes. That way, it can collect the most data. The path can start at any galaxy and end at any galaxy they choose.
Unfortunately, a typical wormhole can only be used once; sending even a small probe through one expends so much energy that the wormhole evaporates and cannot be used again. However, Dr. Henri has noticed that exactly of the wormholes in the cluster are supermassive wormholes. These powerful wormholes can be used up to two times before they evaporate.
What is the largest amount of time the probe can spend in transit?
Subtask 1 [20%]
Subtask 2 [20%]
Subtask 3 [60%]
The first line of input will contain two space-separated integers, and .
The next line will contain space-separated integers, , the indices of the supermassive wormholes.
The next lines will each contain three space-separated integers, , , and , the description of the -th wormhole.
The longest possible time the space probe can spend travelling through wormholes, in minutes.
Sample Input 1
5 1 2 1 4 5 4 3 3 4 2 2 3 5 1
Sample Output 1
Explanation for Sample 1
The optimal path is through the galaxies
1 -> 4 -> 3 -> 4 -> 2.
Sample Input 2
5 4 1 2 3 4 1 4 5 4 3 3 4 2 2 3 5 1
Sample Output 2