DA-F93-CA5-1

Time Limit: 10 Seconds    Memory Limit: 32768 KB

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

Input

این سوال تنها یک ورودی دارد. خط اول از دو عدد N , M تشکیل شده که N تعداد کانال‌ها و M تعداد ایستگاه‌ها است. N و M حداکثر ۲۰۰ هستند. در N خط بعدی، ۳ عدد S,E,C می‌آید که ایستگاه S به ایستگاه‌ E کانالی با ظرفیت C دارد. شماره‌ی ایستگاه‌ها از ۱ شروع می‌شود. ایستگاه‌ ۱، ورودی انرژی و ایستگاه آخر، خروجی انرژی است

Output

بیش‌ترین انرژی که می‌توان انتقال داد را بنویسید

Sample Input

5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10

Sample Output

50

Submit