$G$ یک گراف ساده، وزن‌دار و بدون جهت با $n$‌ راس و $e$ یال می‌باشد که راس‌های آن با اعداد ۱ تا $n$ شماره‌گذاری شده‌اند. هدف ما در این مسئله پیدا کردن کم‌ وزن‌ترین دور با طول فرد در این گراف می‌باشد. وزن یک دور، برابر مجموع وزن یال‌های آن دور می‌باشد؛ هم‌چنین طول یک دور برابر تعداد یال‌‌های آن‌ می‌باشد.

برنامه‌ای بنویسید که:

• مشخصات گراف $G$ را از ورودی بخواند.
• کم‌وزن‌ترین دور با طول فرد را پیدا کند.
• یکی از کم‌وزن‌ترین دورها را در خروجی بنویسد.

• در سطر اول ورودی، دو عدد $n$ و $e$ به ترتیب قرار دارند.($1\leq n \leq 1000$ و $1\leq e \leq 20000$)
• در هر یک از $e$ سطر بعد، سه عدد صحیح مثبت آمده است که با یک فاصله از هم جدا شده‌اند. دو عدد اول شماره رئوس دو سر یک یال را مشخص می‌کنند و عدد سوم وزن این یال را مشخص می‌کند.(وزن هر یال گراف از $10^6$ بیش‌تر نمی‌شود.)

در سطر اول خروجی، ابتدا کم‌ترین وزن یک دور فرد در $G$ و سپس با یک فاصله، طول یکی از کم‌وزن‌ترین دورهای فرد را بنویسید. در سطر بعد، رئوس این دور فرد را به ترتیبی که در دور ظاهر شده‌اند، بنویسید. دقت کنید ممکن است چندین دور فرد با کم‌ترین وزن وجود داشته باشد؛ در این صورت نوشتن هر کدام از آن‌ها درست است. در صورتی که هیچ دور فردی در $G$ وجود نداشت، در تنها سطر خروجی $-1$ چاپ کنید.

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

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