בעיה

במדינת 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