Problem
ان برای جمع آوری قارچ به جنگل قارچ خود می رود.
مسیرهای m گرا در جنگل قارچ وجود دارد که n درخت را به هم متصل می کند. قارچ در هر مسیر رشد می کند. وقتی ان در مسیری قدم می زند، تمام قارچ های آن مسیر را برمی دارد. با این حال، جنگل قارچ چنان خاک حاصلخیز دارد که قارچ ها با سرعت فوق العاده ای رشد می کنند. به محض اینکه En چیدن قارچ ها را در مسیر به پایان رساند، قارچ های جدید رشد می کنند. یعنی بعد از اینکه En برای iمین بار از مسیر عبور کرد، قارچ کمتری نسبت به قبل از این گذرگاه رشد کرد. بنابراین، اگر مسیر در ابتدا دارای x قارچ بود، En در گذر اول x قارچ، x - 1 قارچ در دوم، x - 1 - 2 قارچ در گذر سوم جمع آوری می کند، و به همین ترتیب بر. با این حال، تعداد قارچ ها نمی تواند کمتر از 0 شود.
به عنوان مثال، اجازه دهید ابتدا 9 قارچ در مسیر رشد کنند. سپس تعداد قارچ هایی که En جمع آوری می کند 9، 8، 6 و 3 برای پاس های یک تا چهار است. از پاس پنجم به بعد، En نمی‌تواند چیزی از این مسیر جمع‌آوری کند (اما همچنان می‌تواند در آن راه برود).
En تصمیم گرفت از درخت s شروع کند. حداکثر تعداد قارچ هایی که او می تواند تنها با حرکت در مسیرهای توصیف شده جمع آوری کند چقدر است؟
ورودی:
خط اول شامل دو عدد صحیح n و m (1 ≤ n ≤ 300000، 0 ≤ m ≤ 300000) — تعداد درختان و تعداد مسیرهای جهت دار در جنگل قارچ به ترتیب.
هر یک از خطوط m بعدی شامل سه عدد صحیح x، y و w است (1 ≤ x، y ≤ n، 0 ≤ w ≤ 10
8 ) مسیری را توصیف می کند که از درخت x به درخت y با w قارچ در ابتدا منتهی می شود. مسیرهایی وجود دارد که از یک درخت به یک درخت منتهی می شود و همچنین چندین مسیر وجود دارد که یک جفت درخت را به هم متصل می کند.
خط آخر شامل یک عدد صحیح s (1 ≤ s ≤ n) — موقعیت شروع En.
خروجی:
چاپ یک عدد صحیح — حداکثر تعداد قارچ هایی که En می تواند در راه خود جمع کند.
مثال:
<بدن>
| ورودی |
خروجی |
2 2
1 2 4
2 1 4
1 |
16 |
3 3
1 2 4
2 3 3
1 3 8
1 |
8 |
توضیحات:
در مثال اول، En می‌تواند سه بار دور دایره بچرخد و 4 قارچ جمع آوری کند. پس از آن، قارچی برای جمع آوری En وجود نخواهد داشت.
در مثال دوم En می تواند به درخت 3 برود و 8 قارچ را در مسیر درخت 1 تا درخت 3 بچیند.