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

---

برگزارکنندگان المپیک هنگام برنامه‌ریزی مسابقات با پرسشی روبه‌رو شدند:اختتامیه باید در کدام یک از ساختمان‌های پارک علم و فناوری برگزار شود؟

از آن‌جا که هر حوزه علاقه‌مند بود مراسم تا حد ممکن به محل خودش نزدیک باشد، تصمیم گرفتند مرکزی‌ترین ساختمان پارک را به‌عنوان محل برگزاری انتخاب کنند.

«مرکزی‌ترین ساختمان پارک» به ساختمانی گفته می‌شود که اگر فاصله‌اش را تا تمام ساختمان‌های دیگر حساب کنیم، بیشترین فاصله‌ی آن (یعنی فاصله‌اش تا دورترین ساختمان) در بین همه ساختمان‌ها کمترین مقدار باشد.به بیان ساده، این ساختمان جایی است که حتی دورترین ساختمان هم نسبت به آن تا حد امکان نزدیک‌تر باشد.

ورودی

نقشه‌ی پارک به صورت یک گراف وزن‌دار داده می‌شود.

• در خط اول، دو عدد صحیح \(n\) (تعداد ساختمان‌ها) و \(m\) (تعداد راه‌ها) داده می‌شود. \[0 \le n \le 500\] \[0 \le m \le 130000\]
• در \(m\) خط بعد، هر خط شامل سه عدد \(u\)، \(v\) و \(c\) است که نشان‌دهنده‌ی وجود یک راه دوطرفه بین ساختمان‌های \(u\) و \(v\) با وزن \(c\) است.
• تضمین میشود گراف ساختمان ها همبند است و همچنین فاصله دور ترین ساختمان ها از هم در محدوده int64 قرار دارد.

خروجی

در تنها یک خط شماره‌ی مرکزی‌ترین ساختمان پارک را چاپ کنید. ممکن است بیش از یک ساختمان به‌عنوان مرکزی‌ترین ساختمان پارک شناخته شود. در این صورت، چاپ کردن یکی از آن‌ها به‌تنهایی کافی است.

مثال

ورودی نمونه ۱

4 4
1 2 3
2 3 2
3 4 4
1 4 6

خروجی نمونه ۱

3

• نقشه شامل ۴ ساختمان و ۴ راه است.

• فاصله‌های کوتاه‌ترین مسیر از هر ساختمان به بقیه:

ساختمان	فاصله تا ۱	فاصله تا ۲	فاصله تا ۳	فاصله تا ۴	بیشترین فاصله
1	0	3	5	6	6
2	3	0	2	6	6
3	5	2	0	4	5
4	6	6	4	0	6

• حالا باید ساختمانی پیدا کنیم که «بیشترین فاصله‌اش» کمترین مقدار باشد:

  • برای ساختمان 1 بیشترین فاصله = 6

  • برای ساختمان 2 بیشترین فاصله = 6

  • برای ساختمان 3 بیشترین فاصله = 5

  • برای ساختمان 4 بیشترین فاصله = 6 پس ساختمان 3 مرکزی‌ترین است.

ورودی نمونه ۲

5 6
1 2 2
2 3 2
3 4 2
4 5 2
1 5 10
2 5 3

خروجی نمونه ۲

3