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

• ورودی با $2$ عدد صحیح به صورت $N \ M$ شروع خواهد شد. $N$ تعداد راس‌ها و $M$ تعداد یا‌ل‌های گراف می‌باشد.
• در خط $i$ام از $N$ خط بعدی یک عدد صحیح که وزن راس شماره $i$ را نشان می‌دهد، آمده است.
• در هر یک از $M$ خط بعدی سه عدد طبیعی به صورت $i \ j \ k$ امده است که $i$ و $j$ بیان‌گر راس‌های دو سر یال و $k$ وزن آن یال می‌باشد.
• $1 \leq N \leq 500$
• $0 \leq M \leq 10000$

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

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

• سوال بعد