در این مسئله شما باید کوتاه‌ترین مسیر از راس ۱ به سایر راس‌های گراف را بیابید. یال‌های گراف بی‌جهت هستند.

• در سطر اول ورودی ابتدا $n$ تعداد راس‌های گراف و سپس $e$ تعداد یال‌های آن آمده است.
• در $e$ سطر بعدی در هر سطر ۳ عدد $u$ و $v$ و $c$ نوشته شده است. این بدان معنی است که یک یال بین راس $u$ و $v$ با وزن $c$ وجود دارد.
• $1 \leq n, e \leq 10^5$
• $1 \leq u, v \leq n$
• $1 \leq c \leq 10^4$

• در تنها سطر خروجی $n$ عدد چاپ کنید، که عدد $i$ام فاصله‌ی راس $1$ تا راس $i$ را نشان می‌دهد.
• در صورتی که مسیری از راس $1$ به راس $i$ وجود ندارد، به جای فاصله $-1$ چاپ کنید.

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

• سوال بعد
• سوال قبل