برنامه‌ای بنویسید که در یک DAG (گراف جهت‌دار بدون‌دور) وزن‌دار $n$ راسی و $e$ یالی طولانی‌ترین مسیر جهت‌دار ممکن را پیدا کند. منظور از طولانی ترین، سنگین‌ترین مسیر (و نه پررأس‌ترین مسیر) گراف است.

• در سطر اوّل ورودی ابتدا $n$ و سپس $e$ آمده است.‎
• در e سطر بعدی در هر سطر مشخصات یک یال جهت‌دار آمده است که شامل ابتدا، انتها و وزن آن یال می‌شود.
• رأس‌های ورودی از $1$ تا $n$ هستند. لزومی ندارد که گراف زمینه همبند باشد. وزن یال‌ها مثبت و صحیح‌اند.
• $1 \leq n, e \leq 10^5$

• در سطر اوّل خروجی طول طولانی‌ترین مسیر را بنویسید.
• سپس در سطر دوم خروجی رئوس این مسیر را از ابتدا تا انتها (با یک فاصله خالی بعد از هر عدد) بنویسید. در صورتی که بیش از یک مسیر با طول «طولانی‌ترین» وجود دارد، مسیری را بنویسید که از نظر الفبایی (و نه از نظر تعداد رئوس) کوچک‌ترین باشد. مسیر $P_1$ از مسیر $P_2$ از نظر الفبایی کوچک‌ترست اگر اندیس $x$ وجود داشته باشد که رئوس اوّل تا $x$ هر دو مسیر یکسان باشند و رأس $x+1$ مسیر $P_1$ از رأس $x+1$ مسیر $P_2$ اندیس کم‌تری داشته باشد. اندیس رأسی که وجود ندارد از اندیس تمام رئوس کوچک‌تر است.

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

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