للياقة، $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