Je eine Kuh von $N$ Farmen ($1 \le N \le 1000$), nummeriert mit $1..N$, besucht eine große Kuhparty auf Farm $X$ ($1 \le X \le N$). Insgesamt verbinden $M$ ($1 \le M \le 100,000$) Einbahnstraßen Paare von Farmen; für Straße $i$ benötigt man $T_i$ ($1 \le T_i \le 100$) Zeiteinheiten.

Jede Kuh muss zur Party laufen und nach deren Ende zu ihrer Farm zurückkehren. Jede Kuh ist faul und wählt deshalb eine optimale Route mit der kürzesten Zeit. Da die Straßen nur in eine Richtung führen, kann die Rückroute von der Hinroute abweichen.

Wie groß ist unter allen Kühen die längste Zeit, die eine Kuh für den Hin- und Rückweg zur Party benötigt?

Eingabe

Lies die Eingabe von der Standardeingabe.

• Zeile 1: drei durch Leerzeichen getrennte ganze Zahlen $N$, $M$ und $X$ in dieser Reihenfolge.

Zeilen $2..M+1$: Zeile $i+1$ beschreibt Straße $i$ durch drei durch Leerzeichen getrennte ganze Zahlen $A_i$, $B_i$ und $T_i$. Die Straße führt von Farm $A_i$ zu Farm $B_i$ und benötigt $T_i$ Zeiteinheiten zum Durchlaufen.

Ausgabe

Schreibe die Ausgabe auf die Standardausgabe.

• Zeile 1: eine ganze Zahl, die maximale Laufzeit einer Kuh.

Beispiele

Eingabe 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

Ausgabe 1

10

Hinweis

Kuh $4$ geht direkt zur Party ($3$ Einheiten) und kehrt über die Farmen $1$ und $3$ zurück ($7$ Einheiten), insgesamt $10$ Zeiteinheiten.

Aufgabenquelle: USACO 2007 February Silver