פרה אחת מכל אחת מ־$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

Note

פרה $4$ הולכת ישירות למסיבה ($3$ יחידות) וחוזרת דרך החוות $1$ ו־$3$ ($7$ יחידות), בסך הכול $10$ יחידות זמן.

מקור הבעיה: USACO 2007 February Silver