Công ty vận tải thực hiện vận chuyển hàng hóa qua lại giữa ~n~ thành phố bằng xe tải, các thành phố được đánh chỉ số từ ~1~ đến ~n~. Công ty đã đặt trước chuỗi các khách sạn tại một số thành phố để các tài xế nghỉ ngơi miễn phí sau mỗi ngày làm việc. Công ty muốn tìm một hành trình từ thành phố ~1~ đến thành ~n~ sao cho tài xế luôn nghỉ đêm tại chuỗi khách sạn mà công ty đã đặt và thời gian vận chuyển hàng của hành trình ít ngày nhất có thể.

Bạn hãy lập trình tìm giúp công ty xác định khách sạn ít nhất cần nghỉ lại của hành trình biết rằng mỗi tài xế của công ty lái xe tối đa ~10~ tiếng đồng hồ.

Input

• Dòng đầu ghi một số nguyên ~n~ ~(2 \le n \le 10000)~;

• Dòng thứ hai ghi các số nguyên ~h~ và ~c_1, c_2, \dots, c_h~ ~(1 \le h \le \min(n, 100); 1 \le c_1, c_2, \dots, c_h \le n)~ lần lượt là số lượng khách sạn và số hiệu các thành phố có khách sạn của chuỗi khách sạn của công ty;

• Dòng thứ ba ghi ~m~ ~(1 \le m \le 100000)~ là số lượng các con đường hai chiều nối giữa các thành phố;

• Trong ~m~ dòng tiếp theo mô tả các con đường, mỗi dòng ghi ~3~ số nguyên ~a, b, t~; trong đó ~a, b~ ~(1 \le a, b \le n)~ lần lượt là hai thành phố ở hai đầu con đường, ~t~ ~(1 \le t \le 600)~ là thời gian tính bằng phút để lái xe đi hết con đường đó.

Output

Số khách sạn ít nhất của hành trình. Nếu không tìm được hành trình thỏa mãn điều kiện ghi ~-1~.

Scoring

Sample Input 1

6
3 2 5 3
8
1 2 400
3 2 80
3 4 301
4 5 290
5 6 139
1 3 375
2 5 462
4 6 300

Sample Output 1

2

Sample Input 2

3
0
2
1 2 371
2 3 230

Sample Output 2

-1