You are traversing a nuclear wasteland, trying to make it back to your hideout.
You are currently located at location 1, whereas your hideout is at location .
However, certain locations are covered in nuclear waste, and you would like to
stay as far away as possible from this nuclear waste. This locations are connected
by paths with a particular distance. The danger of a route is the closest you ever
get to a nuclear waste location.
Because of the dangerous nature of the environment, you can only traverse paths in one direction, (however, you consider them going both directions for the purposes of distance from a nuclear waste location.)
In addition, you can also gain a certain amount of food by traversing a path. Traversing the path another time with again yeild that same amount of food!
What is the minimum danger of a route to your hideout. In addition, what is maximum amount of food you can pick up along the way for that minimum amount of danger.
Input
The first line contains the integers and
, the number of locations, number of paths, and number of waste locations respectively.
The second line contains
integers, listing all of the locations which contain a nuclear waste site.
The following
lines contain integers
indicating a directed path from node
to node
with distance
and food
.
The nodes are numbers
through
.
It is guaranteed that there exists path from location 1 to the hideout.
Output
A line containing the smallest danger, and the maximum amount of food. If an infinite amount of food is possible, then write -1 instead.
Constraints
Example 1
Input
3 3 1
2
1 2 3 10
2 3 4 10
1 3 1 1
3 1
Example 2
Input
10 20 2
5 7
1 2 10 0
2 3 10 0
3 4 7 0
4 5 4 0
5 6 10 0
6 7 3 0
7 8 8 0
8 9 10 0
9 10 9 9
10 1 8 0
5 9 2 0
8 7 1 2
7 7 2 0
1 1 1 0
9 10 1 6
8 5 1 0
9 4 3 0
10 6 3 2
2 1 1 0
3 10 3 7
Output
3 7
Example 3
Input
10 20 1
6
1 2 4 0
2 3 4 6
3 4 8 0
4 5 4 0
5 6 3 0
6 7 5 0
7 8 8 0
8 9 1 0
9 10 10 0
10 1 2 7
9 4 3 0
10 3 3 0
8 7 3 0
5 5 1 0
6 3 2 0
2 2 3 9
5 9 3 10
4 10 3 0
8 2 1 0
2 7 2 9
Output
5 -1
Comments