Çəkili istiqamətlənmiş qraf və onun s təpələri verilir.

Qrafının hər bir u təpəsi üçün s təpəsindən u təpəsinə ən qısa yolun uzunluğunu verin.

Giriş verilənləri

Giriş faylının ilk sətri qrafdakı təpələrin və tillərin sayını və başlanğıc təpənin nömrəsini ifadə edən üç tam n, m, s (2 ≤ n ≤ 2000, 1 ≤ m ≤ 5000) ədədlərini ehtiva edir.

Növbəti m sətir qrafın tillərini əks etdirir. Hər bir til üç ədədlə verilir – başlanğıc təpə, son təpə və tilin çəkisi. Tilin çəkisi tam ədəddir və mütləq qiymətcə 1015-i aşmır. Qrafda çox sayda til və dövrlər ola bilər.

Çıxış verilənləri

n sətir verin – hər bir u təpəsi üçün s-dən u-ya ən qısa yolun uzunluğunu verin. Əgər s və u arasında yol yoxdursa, "*" verin. Əgər s və u arasında ən qısa yol yoxdursa, "-" verin.