+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک گراف وزن‌دار و جهت‌دار $G$ با $n$ راس و $m$ یال داریم. راس‌های این گراف با اعداد $1$ تا $n$ شماره‌گذاری شده‌است. از شما می‌خواهیم برنامه‌ای بنویسید تا کوتاه‌ترین فاصله‌ی راس ۱ تا همه‌ی راس‌ها را چاپ کنید. (اگر مسیری از راس شماره‌ی ۱ به راسی وجود نداشت فاصله را با `-1` نشان دهید.) # ورودی در سطر اول ورودی، دو عدد صحیح $n$ و $m$ که با یک فاصله از هم جدا شده‌اند داده می‌شود و به ترتیب تعداد راس‌ها و یال‌های گراف $G$ را نشان می‌دهند. $$1 \leq n \leq 300\, 000$$$$0 \leq m \leq 300\, 000$$ در $m$ سطر بعدی، در هر سطر سه عدد $u$، $v$ و $w$ آمده و نشان دهنده‌ی وجود یک یال از راس $u$ به راس $v$ با وزن $w$ است. $$1 \leq u, v \leq n$$ $$1 \leq w \leq 10^9$$ # خروجی در یک سطر، فاصله‌ی راس ۱ از همه‌ی راس‌ها را به ترتیب چاپ کنید. فاصله‌ی راس ۱ از خودش برابر ۰ است. اگر مسیری از ۱ به راسی وجود نداشت، فاصله را با `-1` نشان دهید. # مثال ## ورودی نمونه ۱ ``` 5 7 1 2 10 2 1 7 1 5 2 3 4 4 1 3 5 3 5 4 5 3 1 ``` ## خروجی نمونه ۱ ``` 0 10 3 7 2 ``` ## ورودی نمونه ۲ ``` 2 5 1 1 5 2 2 3 1 2 2 2 1 3 1 2 4 ``` ## خروجی نمونه ۲ ``` 0 2 ```