A Contest to Meet (ACM) is a reality TV contest that sets three contestants at three random city intersections. In order to win, the three contestants need all to meet at any intersection of the city as fast as possible. The contestants are given communication devices to help them in sharing information about the city (e.g., where the sun is, how far the mountains are, etc.). It should be clear that the contestants may arrive at the intersections at different times, in which case, the first to arrive can wait until the others arrive. Moreover, it is guaranteed that there is a path between any pair of intersections. From an estimated walking speed for each one of the three contestants, ACM wants to determine the minimum time that a live TV broadcast should last to cover their journey regardless of the contestants’ initial positions and the intersection they finally meet. You are hired to help ACM answer this question. You may assume the following: • Each contestant walks at a given estimated speed. • The city is a collection of intersections in which some pairs are connected by bidirectional streets that the contestants can use to traverse the city. Input The input consists of several test cases. The first line of each test case contains two blank-separated integer values N and S, indicating the number of intersections and the number of streets in the city, respectively (1 ≤ N ≤ 100, 0 ≤ S ≤ 9000). Then follow S lines, each one with three blank-separated integer values i, j, and d (0 ≤ i < N, 0 ≤ j < N, i ̸= j, 1 ≤ d ≤ 200), meaning that there is a street of length d meters connecting the i-th and the j-th intersections. Note that intersections are indexed from 0 to N − 1. You can assume that there is at most one street connecting any pair of intersections and that the input lists a street exactly once. At the end of each test case there is one line with three blank-separated integer values sA, sB, sC (50 ≤ sA, sB, sC ≤ 100), representing the walking speed of each of the three contestants, in meters per minute. Output For each test case, print a single line with an integer indicating the minimum number of minutes that will pass before the three contestants can meet, if they start to walk immediately after the show starts. Remember that the contestants can start at any random (unknown) intersection and can decide to meet at any intersection: you need to account for the worst case scenario. The answer should be given rounding decimals to the next integer (e.g., 2.9 minutes rounds up to 3 minutes and 3.2 minutes rounds up to 4 minutes). Sample Input 21 0 1 150 60 50 75 32 1 0 100
2/2 1 2 80 60 80 50 45 0 1 200 0 2 200 0 3 200 2 1 200 2 3 200 50 100 100 Sample Output 3 4 8