Есеп

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