לכושר, $N$ פרות ($(2 \le N \le 1,000,000)$) רצות שליחים ב־$T$ שבילים ($(2 \le T \le 100)$) במרעה.

כל שביל מחבר שני צמתים שונים ($(1 \le I1_i \le 1,000; 1 \le I2_i \le 1,000)$), כל צומת קצה של שני שבילים לפחות. אורך $length_i$ ($(1 \le length_{i} \le 1,000)$) והקצוות ידועים, אין שני שבילים ישירים לאותו זוג. זה גרף מתמטי.

$N$ פרות עומדות בצמתים, אולי כמה באחד. צריך סידור להעברת מקל פרה אחרי פרה לסיום הנכון.

עזרו בסידור: דרך קצרה ביותר ממוצא $S$ לסיום $E$ דרך בדיוק $N$ שבילים.

קלט

• שורה $1$: השלמים $N$, $T$, $S$, $E$ מופרדים.

• שורות $2..T+1$: שורה $i+1$ מתארת שביל $i$ בשלמים $length_i$, $I1_i$, $I2_i$ מופרדים.

פלט

• שורה $1$: שלם אחד, מרחק קצר ביותר $S$ אל $E$ דרך בדיוק $N$ שבילים.

דוגמאות

קלט 1

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

פלט 1

10

מחבר הבעיה: Erik Bernhardsson, 2003