در خط اول ورودی ابتدا $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 بنویسید.