در خط اول ورودی ابتدا $n$ تعداد رأس‌ها، سپس $e$ تعداد یال‌ها و $s$ یعنی رأس مبدأ آمده‌است.

در $e$ خط بعد در هر خط سه عدد $x$، $y$ و $w$ آمده که می‌گوید بین رأس‌های $x$ و $y$، یالی با وزن $w$ وجود دارد.

تمام اعداد ورودی و خروجی در int جا می‌شوند.

$1 \leq n \leq 1000$

$1 \leq e \leq 10000$

شما باید گراف ورودی را تحلیل کنید، اگر دور منفی داشت در خروجی، در یک خط بنویسید: ‌BAD.

در غیر این‌صورت باید $n$ عدد در خروجی نوشته شود که به ترتیب فاصله $s$ با رأس‌های گراف است. اگر فاصله از یکی از رأس‌ها بی‌نهایت بود، به‌جای عدد، INF بنویسید.

محدودیت زمان: ۱ ثانیه

محدودیت حافظه: ۲۵۶ مگابایت