ستحضر بقرة من كل مزرعة من المزارع $N$ ($1 \le N \le 1000$)، المرقمة $1..N$، حفلة الأبقار الكبيرة في المزرعة $X$ ($1 \le X \le N$). هناك إجمالًا $M$ ($1 \le M \le 100,000$) طريقًا أحادي الاتجاه تصل بين أزواج المزارع؛ يستغرق اجتياز الطريق $i$ مقدار $T_i$ ($1 \le T_i \le 100$) وحدة زمن.

يجب أن تمشي كل بقرة إلى الحفلة، ثم تعود إلى مزرعتها عند انتهائها. كل بقرة كسولة، لذا تختار مسارًا أمثل بأقصر وقت. لأن الطرق أحادية الاتجاه، قد يختلف مسار العودة عن مسار الذهاب.

من بين جميع الأبقار، ما أطول وقت يجب أن تقضيه بقرة في المشي إلى الحفلة والعودة؟

الإدخال

اقرأ الإدخال من الإدخال القياسي.

• السطر 1: ثلاثة أعداد صحيحة مفصولة بمسافات، هي $N$ و$M$ و$X$ على الترتيب.

الأسطر $2..M+1$: يصف السطر $i+1$ الطريق $i$ بثلاثة أعداد صحيحة مفصولة بمسافات: $A_i$ و$B_i$ و$T_i$. يمتد الطريق من المزرعة $A_i$ إلى المزرعة $B_i$ ويستغرق اجتيازه $T_i$ وحدة زمن.

الإخراج

اكتب الإخراج إلى الإخراج القياسي.

• السطر 1: عدد صحيح واحد، وهو أكبر وقت مشي لأي بقرة.

أمثلة

الإدخال 1

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

الإخراج 1

10

ملاحظة

تذهب البقرة $4$ مباشرة إلى الحفلة ($3$ وحدات) وتعود عبر المزرعتين $1$ و$3$ ($7$ وحدات)، بمجموع $10$ وحدات زمن.

مصدر المسألة: USACO 2007 February Silver