Cho một đồ thị gồm ~n~ đỉnh và ~m~ cạnh có hướng có trọng số.

Với mỗi đỉnh ~i~, hãy tính độ dài của quãng đường ngắn nhất để đi xuất phát từ đỉnh ~1~, đi qua đỉnh ~i~ và quay về đỉnh ~1~.

Input

• Dòng thứ nhất chứa ~2~ số nguyên dương ~n,m~.
• ~m~ dòng sau mỗi dòng gồm ~3~ số nguyên dương ~u,v,w~ ~(1 \le u, v \le n, u \neq v)~, miêu tả cạnh gồm đỉnh ~u~ nối với đỉnh ~v~ có trọng số ~w~.

Output

• Gồm ~n~ dòng, dòng thứ ~i~ in ra độ dài của quãng đường ngắn nhất để đi xuất phát từ đỉnh ~1~, đi qua đỉnh ~i~ và quay về đỉnh ~1~. Nếu không có quãng đường nào như vậy thì in ra ~-1~.

Constraints

• ~1 \le n,n \le 2*10^5~.
• ~1 \le w \le 10^9~.

Subtasks

• Subtask ~1~: Nếu tồn tại cạnh ~(u,v,w)~ thì sẽ có cạnh ~(v,u,w)~. ~(30\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(70\%)~

Sample Input 1:

5 7
1 4 5
1 5 3
3 5 2
5 4 10
5 1 7
3 2 5
2 1 1

Sample Output 1:

-1
-1
-1
10

Sample Input 2:

2 1
2 1 10

Sample Output 2:

-1

Cho đồ thị vô hướng có trọng số gồm ~n~ đỉnh và ~m~ cạnh không chứa khuyên, mỗi cạnh có dạng ~(u,v,c)~, tức là cạnh nối hai đỉnh ~u~ và ~v~ có trọng số ~c~.

Với mỗi cạnh, hãy xác định xem cạnh đó có nằm trong mọi cây khung nhỏ nhất của đồ thị hay không.

Input:

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5, n-1 \le m \le 2*10^5)~
• ~m~ dòng tiếp theo, mỗi dòng gồm ~3~ số nguyên ~u_i,v_i,w_i~ ~(1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^9)~ - lần lượt là hai đỉnh và trọng số của cạnh thứ ~i~.
• Dữ liệu đảm bảo đồ thị liên thông.

Output:

• In ra ~m~ xâu kí tự, trong đó xâu thứ ~i~ là "Yes" nếu cạnh thứ ~i~ thuộc toàn bộ các cây khung nhỏ nhất của đồ thị, "No" nếu ngược lại.

Constraints:

• Có ~10\%~ số test ứng với ~m \le 20~
• Có ~20\%~ số test ứng với ~m \le 300~
• Có ~20\%~ số test ứng với ~m \le 4000~;
• Có ~20\%~ số test ứng với trọng số của mọi cạnh phân biệt.
• ~30\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input 1

5 7
4 3 2
1 2 2
1 4 7
2 5 1
1 3 9
2 4 9
2 3 7

Output 1

Yes Yes No Yes No No No 

Cho một cây vô hướng gồm ~n~ đỉnh ~(1 \le n \le 1e5)~ và ~m~ đỉnh đặc biệt ~(1 \le m \le n)~, kèm một số ~k~ nguyên dương bất kì ~(1 \le k \le n)~. Một đỉnh ~u~ được gọi là tốt nếu như với mọi đỉnh ~v~ thuộc tập ~m~ đỉnh đặc biệt, ta luôn có ~dist(u,v) \le k~. Ở đây, ~dist(u,v)~ là khoảng cách của đỉnh ~u~ và ~v~ trên cây, hay bằng số cạnh trên đường đi ngắn nhất từ đỉnh ~u~ tới đỉnh ~v~. Hãy đếm xem có bao nhiêu đỉnh được coi là "tốt".

Input:

• Dòng đầu gồm 3 số ~n,m,k. (1 \le m \le n \le 10^5, 1 \le k \le 10^5).~
• ~n-1~ dòng sau mỗi dòng gồm 2 số ~u,v (1 \le u,v \le n)~ là cạnh nối từ đỉnh ~u~ tới ~v~.
• Dòng cuối gồm ~m~ số miêu tả các đỉnh đặc biệt.

Output:

• Số đỉnh tốt.

Sample Test

Input:

6 2 3 
1 5 
2 3 
3 4 
4 5 
5 6
1 2

Output:

3

Giải thích:

• 3 đỉnh tốt là đỉnh 3,4,5.

Ràng buộc

• Subtask 1: ~n <= 500.~ (50%)
• Subtask 2: Với mỗi thành phố, chỉ có tối đa 2 con đường nối tới các thành phố khác.
• Subtask 3: Không giới hạn gì thêm. (20%).

Vào một ngày đẹp trời, bỗng dưng Thinkies đi lạc vào một mê cung. Mê cung được biểu diễn dưới dạng một ma trận ~n*m.~ Ô hàng ~i~, cột ~j~ của mê cung được gọi là ô ~(i,j)~. Mê cung này rất đặc biệt, có ~p~ ô lối vào và ~q~ ô lối ra. Thinkies có thể xuất phát từ một ô bất kì trong ~p~ ô lối vào đó, và có thể thoát ra bằng cách đi tới một ô bất kì trong ~q~ ô lối ra. Mỗi ô đều chứa những giá trị riêng, ô ~(i,j)~ có giá trị ~a(i,j)~. Từ một ô ~(i,j)~ bất kì, Thinkies có thể di chuyển theo 2 cách (đều mất một đơn vị thời gian):

• Di chuyển sang ô kề cạnh với nó (từ ô ~(i,j)~ có thể tới ô ~(u,v)~ nếu ~(u,v)~ kề cạnh với ~(i,j)~ và ~a(u,v) \neq 0~).
• Sử dụng phép teleport, di chuyển sang ô ~(u,v)~ nếu ~u*v = a(i,j)~ và ~a(u,v) \neq 0~. Tuy nhiên, Thinkies chỉ có thể sử dụng được ~k~ lần phép teleport này mà thôi. Lưu ý, nếu trên các ô lối vào hoặc lối ra có giá trị a(u,v) = 0 thì ta sẽ không thể nào xuất phát hoặc đi vào ô đó. Hãy tìm cách đưa Thinkies ra khỏi mê cung sớm nhất có thể!

Input

• Dòng đầu gồm 3 số ~n,m,k (1 \le n, m \le 1000, k \le 3)~
• ~n~ dòng sau, mỗi dòng gồm m số ~a(i,j)~ biểu hiện mê cung
• Dòng tiếp theo gồm 2 số tự nhiên ~p,q (p+q \le n*m)~.
• ~p~ dòng tiếp theo mỗi dòng gồm một cặp số ~(i,j)~ thể hiện các ô là lối vào.
• ~q~ dòng tiếp theo mỗi dòng gồm một cặp số ~(i,j)~ thể hiện các ô là lối ra.

Output:

Số đơn vị thời gian ít nhất để Thinkies có thể ra khỏi mê cung, nếu không thể thoát ra in ra số ~-1~.

Sample Test 1

Input:

3 3 1
6 1 1
1 1 1
1 1 1
1 1
1 1
3 3

Output:

2

Sample Test 2

Input:

2 2 3
0 1 
2 1
1 1
1 1
2 1 

Output:

-1

Sample Test 3

Input:

2 2 3
2 1 
0 1
1 1
1 1
2 1 

Output

-1

Giải thích

• Ở test 2, do ô ~(1,1)~ có ~a(1,1) = 0~ nên ta không thể xuất phát từ ô đó, nên sẽ không thể đi ra.
• Ở test 3, do ô ~(2,1)~ có ~a(2,1) = 0~ nên ta không thể đi vào ô đó, nên không thể thoát ra mê cung.

Ràng buộc

~a(i, j) \le 6 * 10 ^ 6~

• Subtask 1: ~n \le 50, m \le 50, k = 0~. (20%)
• Subtask 2: ~n \le 1000, m \le 1000, k = 0~. (30%)
• Subtask 3: ~n \le 50, m \le 50.~ (20%)
• Subtask 4: ~n,m \le 1000, k \le 3.~ (30%)

Ở một đất nước nọ, có ~n~ thành phố được kết nối với nhau bằng ~n-1~ con đường 2 chiều, đảm bảo rằng từ một thành phố bất kì có thể tới được tất cả các thành phố khác.

Thành phố thứ ~i~ có một giá trị ~a_i~, là độ "đẹp của thành phố đó. Các giá trị a_i này có thể giống nhau, tức là các thành phố có thể có độ đẹp ngang nhau.

Một vị khách du lịch khi tới đất nước này chơi trong ~k (1 \le k \le 10^{18})~ ngày. Hiện tại, vị khách ấy đang ở thành phố 1. Cách di chuyển của vị khách này rất đặc biệt, ví dụ ở ngày thứ i và vị khách đang ở thành phố ~u~ (ở ngày đầu thì anh ta ở thành phố 1), anh sẽ đi tới thành phố ~v~ khác ~u~, sao cho ~a_v - dist(u,v)~ là lớn nhất (~dist(u,v)~ là đường đi ngắn nhất từ thành phố ~u~ tới ~v~). Nếu có nhiều thành phố thỏa mãn điều kiện trên, anh ta sẽ đi tới thành phố có chỉ số nhỏ nhất.

Là một người yêu thích tin học, vị khách đưa ra một yêu cầu trước khi tham quan, đó là hãy tính xem, sau ~k~ ngày, anh ta sẽ ở thành phố nào. Hãy lập trình và giải bài toán này giúp anh ấy.

Input

• Dòng đầu gồm 2 số ~n~ và ~k~, lần lượt là số thành phố và số ngày vị khách ở ~(1 \le n \le 3 \times 10^5, 1 \le k \le 10^{18})~.
• Dòng sau gồm ~n~ số miêu tả dãy ~a~. ~(0 \le a_i \le 10^9 \; \forall \; 1 \le i \le n).~
• ~n-1~ dòng sau, mỗi dòng gồm 2 số ~u,v (1 \le u,v \le n)~ miêu tả con đường 2 chiều nối ~u~ và ~v~.

Output

In ra thành phố mà anh ta sẽ đến sau ~k~ ngày.

Ràng buộc

• Subtask 1: ~n \le 1000, k \le 10^5~ (20%)
• Subtask 2: ~n \le 1000, k \le 10^{18}~ (15%)
• Subtask 3: ~n \le 300000, k \le 10^5~ (50%)
• Subtask 4: ~n \le 300000, k \le 10^{18}~ (15%)

Sample Test

Input:

5 4
1 1 3 2 4
1 2
1 3
2 4
2 5

Output:

5

Giải thích:

• Vị khách sẽ đi theo thứ tự 1 --> 3 --> 5 --> 2 --> 5