Trung tâm phân phối \(S\) là nơi tập kết rất nhiều nông sản. Mỗi ngày, trung tâm cần cử các xe giao hàng để vận chuyển nông sản đến các thành phố/điểm bán lẻ khác nhau. Mỗi xe đi đến một địa điểm riêng biệt. Các thành phố được kết nối với nhau và với trung tâm bằng những tuyến đường. Mỗi tuyến đường có một thời gian di chuyển nhất định.

Hãy tìm ra thời gian di chuyển ngắn nhất từ trung tâm phân phối (\(S\)) đến tất cả các thành phố/điểm bán lẻ khác trong mạng lưới. Việc này giúp tài xế giao hàng hiệu quả nhất, đảm bảo nông sản tươi ngon đến tay khách hàng nhanh chóng.

Input

• Dòng 1: Ba số nguyên \(N, M, S\).
  • \(N\): Tổng số địa điểm (bao gồm Trung tâm phân phối và các thành phố/điểm bán lẻ), được đánh số từ \(1\) đến \(N\).
  • \(M\): Số lượng tuyến đường kết nối các địa điểm.
  • \(S\): Trung tâm phân phối nông sản.
• \(M\) dòng tiếp theo: Mỗi dòng gồm ba số nguyên \(U, V, W\).
  • \(U, V\): Hai địa điểm được kết nối bởi một tuyến đường.
  • \(W\): Thời gian di chuyển giữa \(U\) và \(V\).

Output

• Ghi \(N\) dòng, trong đó dòng thứ \(i\) in ra thời gian di chuyển ngắn nhất từ Trung tâm phân phối \(S\) đến địa điểm \(i\). Nếu không có đường đi đến một địa điểm nào đó, in ra \(-1\).

Example

5 6 1
1 2 10
1 3 30
2 3 5
2 4 20
3 5 15
4 5 10

1: 0
2: 10
3: 15
4: 30
5: 30

Ràng buộc

• \(1 \leq N \leq 10^3\)
• \(1 \leq S \leq 10^3\)
• \(1 \leq M \leq N \times (N-1)/2\)
• \(1 \leq W \leq 10^9\)