Karaoke Meetup

Time limit8sMemory limit512 MB

Summary

In a weighted tree, some vertices are marked as houses. For each vertex compute the ratio of the nearest marked vertex distance to the farthest, and output the maximum ratio as a reduced fraction.

Level: Hard9 of 10
Topics: Tree, DFS, Divide and conquer, Greedy
Solved: No attempts yet

Problem

The judges of the South Pacific Programming Contest are planning their next secret karaoke meetup and are looking for a place to hold it. Last time they asked Timothy to pick the location, and of course he picked somewhere really close to his house, far from everyone else's. This year you want to pick a fair meeting location.

All the judges live in the same city. The city consists of various locations where the meeting could be held, and roads that connect pairs of locations. The city is built so that for each pair of locations, there is exactly one path between them. Each road has a length and can be used to travel in either direction. You consider a meeting point fair if the distances from each judge's house are similar. For each location, its fairness score is the ratio A/B, where A is the minimum distance from the location to any judge's house and B is the largest distance. What is the maximum fairness score over all vertices?

Input

The first line contains two integers n (2 ≤ n ≤ 200 000), the number of locations in the city, and k (2 ≤ k ≤ n), the number of judges.

The next k lines describe the locations of the judges' houses. Each of these lines contains a single integer ℓ (1 ≤ ℓ ≤ n), the location of this judge's house. No two judges live at the same location.

The next n − 1 lines describe the roads in the city. Each of these lines contains three integers u (1 ≤ u ≤ n), v (1 ≤ v ≤ n), and w (1 ≤ w ≤ 10^9), denoting a road between locations u and v with a length of w.

Output

Display the maximum fairness score as a reduced fraction.

Examples4

Example 1
Input
```
3 2
2
3
1 2 1
1 3 1
```
Expected output
```
1/1
```
Example 2
Input
```
2 2
1
2
1 2 10
```
Expected output
```
0/1
```
Example 3
Input
```
5 3
5
2
4
3 1 1
1 4 1
1 2 1
3 5 1
```
Expected output
```
1/2
```

Example 4

Input

Expected output

5/16