+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- دیجی‌کالا انبارهای متفاوتی دارد و از طرفی خود فروشندگان هم می‌توانند انبارهای خود را داشته باشند،‌ اما یک انبار اصلی وجود دارد که به آن انبار دانش می‌گوییم. میان برخی از این انبارها جاده‌هایی وجود دارد که هزینه‌ی عبور از این جاده‌ها مشخص است. دیجی‌کالا برای جابه‌جایی کالاها میان انبارها با شرکتی به نام «ترانزیت برادران سلطانلو به جز سلطان کوچیکه» قرارداد بسته و آن‌ها به ازای هر جابه‌جایی هزینه‌ای از دیجی‌کالا دریافت می‌کنند. اما این شرکت قانون عجیبی برای جابه‌جایی دارد. این قانون از این قرار است که در هر حرکت باید از ۲ جاده عبور کرد مثلا برای جابه‌جایی از انبار $i$ به انبار $k$، ابتدا باید از انبار $i$ به انبار $j$ و سپس از انبار $j$ به انبار $k$ حرکت کرد و در نهایت هزینه‌‌ای که بابت این مسیر، دریافت می‌کند برابر مربع مجموع هزینه‌ی هرکدام از مسیرهاست، یا به عبارتی: $${(cost(i,j) + cost(j,k))}^2$$ طبق این تعریف، ممکن است بین دو انبار هیچ مسیری وجود نداشته باشد! چون هر مسیر شامل تعدادی حرکت است (که هر حرکت دقیقا شامل ۲ جاده است) و مجموع هزینه‌ی این حرکت‌ها برابر است با هزینه‌ای که شرکت باید به برادران سلطانلو بپردازد. حال از شما خواسته می‌شود که کم‌ترین هزینه‌ی جابه‌جایی از انبار اصلی دانش(انبار ۱) به باقی انبارها را بیابید. توجه داشته باشید که ممکن است نتوانید مسیری میان انبار اصلی و برخی از انبارها بیابید. در آن صورت این هزینه را ۱- برگردانید. # ورودی در خط اول ۲ عدد $n$ و $m$ آمده است که به ترتیب تعداد انبارها و تعداد راه‌هاست. میان هر ۲ انبار حداکثر یک راه داریم و انباری به خودش راهی ندارد. $$2 \leq n \leq 100 \ 000$$ $$1 \leq m \leq 200 \ 000$$ در $m$ خط بعدی در هر خط به ترتیب سه عدد $u$ و $v$ و $w$ آمده که نشان دهنده‌ی راهی دوطرفه بین $u$ و $v$ است که هزینه‌ی آن $w$ است. $$1 \leq w \leq 50$$ $$1 \leq u \neq v \leq n$$ تضمین می‌شود هر راه حداکثر یکبار ورودی داده می‌شود. # خروجی در تنها خط خروجی به ازای انبار $i$ اگر مسیری درست برای جابه‌جایی (با توجه به شروط گفته شده) از انبار یک به انبار $i$ وجود نداشت عدد ۱- و اگر وجود داشت کم ترین هزینه‌ی ممکن برای جابه‌جایی از انبار ۱ به انبار $i$ را چاپ کنید. دقت کنید فاصله‌ی هر انبار از خودش برابر صفر میباشد. # مثال‌ها ## نمونه ورودی ۱ ``` 3 2 1 2 4 2 3 2 ``` ## نمونه خروجی ۱ ``` 0 -1 36 ``` در این مثال، مسیری درست برای رسیدن از ۱ به ۲ وجود ندارد و عدد ۱- برمی‌گردد. برای رسیدن از انبار ۱ به انبار ۳ کافیست جاده‌های انبار ۱ به انبار ۲ و انبار ۲ به انبار ۳ طی شوند و جمع هزینه آن‌ها برابر مربع مجموع ۴ و ۲ یعنی ۳۶ است. ## نمونه ورودی ۲ ``` 4 4 1 2 2 2 3 3 3 4 6 2 4 5 ``` ## نمونه خروجی ۲ ``` 0 130 25 49 ```

حل سؤال در بانک سؤالات