المسألة

في دولة JOI توجد $n$ جزيرة، وكل جزيرة مرقمة من $1$ إلى $n$. يجري حالياً في دولة JOI تطوير شبكة خطوط بحرية تربط بين هذه الجزر.

أنت تعمل في مركز تذاكر يتعامل مع تذاكر السفن. في دولة JOI هناك الكثير من الأشخاص الذين يرغبون في السفر بين الجزر بالسفن بأقل تكلفة ممكنة؛ وهم يكتبون جزيرة الانطلاق وجزيرةالوجهة في قسيمة طلب ويرسلونها إليك.

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

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

الإدخال

في السطر $1$ من الإدخال يُكتب عددان صحيحان ($2$) هما $n, k$ ($1 \le n \le 100, 1 \le k \le 5000$). يشير هذا إلى أن عدد الجزر هو $n$ وأن الإدخال يتكون من $k + 1$ من الأسطر. في السطر $(i + 1)$ ($1 \le i \le k$) تُكتب $3$ أو $4$ أعداد صحيحة مفصولة بمسافات.

• عندما يكون الرقم الأول هو $0$، يمثل هذا السطر قسيمة طلب من زبون. يُكتب في هذا السطر $3$ أعداد صحيحة $0, a, b$ ($1 \le a \le n, 1 \le b \le n, a \ne b$) مفصولة بمسافات. يعني هذا أن زبوناً أرسل قسيمة طلب نقطة انطلاقها الجزيرة $a$ ووجهتها الجزيرة $b$.
• عندما يكون الرقم الأول هو $1$، يمثل هذا السطر معلومات تشغيل سفينة بدأت العمل حديثاً. يُكتب في هذا السطر $4$ أعداد صحيحة $1, c, d, e$ ($1 \le c \le n, 1 \le d \le n, c \ne d, 1 \le e \le 1000000$). يعني هذا أن سفينة تعمل ذهاباً وإياباً بين الجزيرة $c$ والجزيرة $d$ قد بدأت العمل حديثاً، وأن أجرة هذه السفينة من الجزيرة $c$ إلى الجزيرة $d$ ومن الجزيرة $d$ إلى الجزيرة $c$ تساوي $e$ في كلا الاتجاهين. بالنسبة لقسائم الطلبات التي تلي هذا السطر، يجب الرد مع أخذ هذه السفينة في الحسبان أيضاً.

في المرحلة الابتدائية، نفترض أن هناك $0$ سفينة قيد التشغيل. في الإدخال، لا يتجاوز عدد الأسطر التي تمثل معلومات تشغيل السفن $1000$ سطر. لاحظ أيضاً أنه قد تعمل عدة سفن بين نفس الزوج من الجزر.

الإخراج

ليكن $m$ هو عدد الأسطر التي تمثل قسائم الطلبات في الإدخال. يتكون الإخراج من $m$ سطراً، وفي السطر $i$ ($1 \le i \le m$) اكتب عدداً صحيحاً يمثل الرد على قسيمة الطلب رقم $i$. أي إذا كان من الممكن السفر بين نقطة الانطلاق والوجهة في قسيمة الطلب رقم $i$ عن طريق التبديل بين عدة سفن، فاكتب القيمة الصغرى لمجموع الأجور، وإذا كان السفر مستحيلاً فاكتب $-1$.

أمثلة الإدخال والإخراج

مثال الإدخال 1

3 8
1 3 1 10
0 2 3
1 2 3 20
1 1 2 5
0 3 2
1 1 3 7
1 2 1 9
0 2 3

مثال الإخراج 1

-1
15
12

مثال الإدخال 2

5 16
1 1 2 343750
1 1 3 3343
1 1 4 347392
1 1 5 5497
1 2 3 123394
1 2 4 545492
1 2 5 458
1 3 4 343983
1 3 5 843468
1 4 5 15934
0 2 1
0 4 1
0 3 2
0 4 2
0 4 3
0 5 3

مثال الإخراج 2

5955
21431
9298
16392
24774
8840