Cho n địa điểm, giữa 2 địa điểm có thể có đường đi trực tiếp. Có tất cả m đường đi trực tiếp.

Tìm đường đi nhỏ nhất từ điểm s đến tất cả các điểm còn lại.

INPUT

Dòng đầu là 3 số nguyên dương: n, m, s (n ≤ ~10^5~; m ≤ ~2.10^5~; 1 ≤ s ≤ n)

m dòng tiếp theo, mỗi dòng gồm 3 số nguyên dương u, v, c cho biết có đường đi nối 2 địa điểm u và v với độ dài c. (1 ≤ u, v ≤ n; c ≤ ~10^4~).

OUTPUT

Ghi ra n số trên cùng một dòng: số thứ i là độ dài đường đi ngắn nhất từ đỉnh s đến điểm i. Nếu không có đường đi từ s đến điểm i thì ghi ra -1.

Ví dụ:

Input

5 7 2
1 3 8
1 5 7
1 4 12
2 5 11
2 4 5
3 5 16
5 4 4

Output:

16 0 24 5 9

Có N thành phố. Biết rằng đường đi giữa hai thành phố bất kì (nếu có) đều là đường hai chiều. Sơ đồ mạng lưới giao thông của N thành phố này cho bởi bảng đối xứng A[i,j]. Trong đó: A[i,j] là độ dài đường đi từ thành phố i đến thành phố j. A[i,j]=0 nếu không có đường đi từ thành phố i đến thành phố j. A[i,j]=A[j,i] và A[i,i]=0. A[i,j] nguyên, không âm.

Tìm đường đi ngắn nhất giữa 2 thành phố P và Q.

INPUT

Dữ liệu vào gồm N+2 dòng:

Dòng đầu là số N (N nguyên dương, N ≤ 50);

Dòng i+1 (1 ≤ i ≤ N) ghi N số nguyên A[i,1], A[i,2,...A[i,N].

Dòng N+2 ghi 2 số P và Q.

OUTPUT

Xuất ra màn hình cho biết độ dài đường đi ngắn nhất từ P đến Q và sơ đồ đường đi hoặc thông báo "Khong co duong di".

Ví dụ:

Input

6
0 5 0 0 0 9
5 0 6 0 0 0
0 6 0 7 0 0
0 0 7 0 8 0
0 0 0 8 0 9
9 0 0 0 9 0
1 5

Output:

18
1 6 5

Cho n địa điểm, giữa 2 địa điểm có thể có đường đi trực tiếp. Có tất cả m đường đi trực tiếp.

Tìm đường đi ngắn nhất từ địa điểm s đến địa điểm t.

INPUT

Dòng đầu là 4 số nguyên dương: n, m, s, t (n ≤ ~10^5~; m ≤ ~2.10^5~; 1 ≤ s, t ≤ n)

m dòng tiếp theo, mỗi dòng gồm 3 số nguyên dương u, v, c cho biết có đường đi nối 2 địa điểm u và v với độ dài c. (1 ≤ u, v ≤ n; c ≤ ~10^4~).

OUTPUT

Dòng 1 ghi ra độ dài đường đi, nếu không có đường đi ghi ra -1;

Dòng 2 ghi ra các địa điểm trên đường đi ngắn nhất từ s đến t.

Ví dụ:

Input

5 7 2 1
1 3 8
1 5 7
1 4 12
2 5 11
2 4 5
3 5 16
5 4 4

Output:

16
2 4 5 1

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

Tìm đường đi nhỏ nhất từ đỉnh s đến tất cả các đỉnh còn lại.

INPUT

Dòng đầu là 3 số nguyên dương: n, m, s (n ≤ ~10^4~; m ≤ ~2.10^5~; 1 ≤ s ≤ n)

m dòng tiếp theo, mỗi dòng gồm 3 số nguyên u, v, c cho biết có cung u-v với trọng số c. (1 ≤ u, v ≤ n; |c| ≤ ~10^4~).

Lưu ý: trọng số có thể âm.

OUTPUT

Ghi ra n số trên cùng một dòng: số thứ i là độ dài đường đi ngắn nhất từ đỉnh s đến đỉnh i. Nếu không có đường đi từ s đến đỉnh i thì ghi ra -1.

Ví dụ:

Input

5 7 2
1 3 8
1 5 -7
4 1 12
2 5 8
2 4 5
3 5 1
5 4 -4

Output:

16 0 24 4 8 

Bài khó hơn

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

Tìm đường đi nhỏ nhất từ đỉnh s đến đỉnh t.

INPUT

Dòng đầu là 4 số nguyên dương: n, m, s, t (n ≤ ~10^4~; m ≤ ~10^6~; 1 ≤ s, t ≤ n)

m dòng tiếp theo, mỗi dòng gồm 3 số nguyên u, v, c cho biết có cung u-v với trọng số c. (1 ≤ u, v ≤ n; |c| ≤ ~10^4~).

Lưu ý trọng số có thể âm.

OUTPUT

Ghi ra các đỉnh trên đường đi ngắn nhất từ s đến t. Nếu không có đường đi thì ghi ra số -1.

Ví dụ:

Input

5 7 2 3
1 3 8
1 5 -7
4 1 12
2 5 8
2 4 5
3 5 1
5 4 -4

Output:

2 5 4 1 3

Bài dễ hơn