Yêu cầu:

Cho một đồ thị vô hướng liên gồm n đỉnh và m cạnh, các đỉnh được đánh số từ 1 tới n và các cạnh được đánh số từ 1 tới m. Hãy tìm đường đi ngắn nhất bắt đầu từ đỉnh X tới các đỉnh còn lại.

Input

• Dòng 1: Chứa ba số n, m, X. (n<=10⁵ , m<=2*10⁵ , X<=n)
• M dòng tiếp theo: Dòng thứ i có dạng 3 số nguyên dương u, v, w. Trong đó u, v là chỉ số hai đỉnh đầu mút của cạnh thứ i, w là giá trị của cạnh u,v đó. (w<=10⁹)

Output

In ra n dòng, dòng thứ i là đường đi có giá trị nhỏ nhất từ đỉnh X tới đỉnh i. Trường hợp không thể đến được thì in ra -1.