Deskripsi Masalah

Di negara JOI terdapat $n$ pulau, dan masing-masing pulau diberi nomor dari $1$ hingga $n$. Saat ini, di negara JOI sedang dilakukan pengembangan jaringan rute pelayaran yang menghubungkan antarpulau.

Anda bekerja di pusat tiket yang menangani tiket kapal. Di negara JOI, ada banyak orang yang ingin bepergian antarpulau menggunakan kapal dengan biaya semurah mungkin; mereka menuliskan pulau keberangkatan dan pulau tujuan pada formulir pemesanan lalu mengirimkannya kepada Anda.

Tugas Anda adalah, segera setelah menerima formulir pemesanan dari pelanggan, menghitung ongkos termurah di antara rute-rute yang menghubungkan pulau keberangkatan dan pulau tujuan dengan berpindah-pindah beberapa kapal, lalu memberitahukannya kepada pelanggan. Namun, bergantung pada rencana perjalanan, ada kalanya perjalanan menggunakan kapal tidak dapat dilakukan. Pada saat itu, Anda harus memberi tahu pelanggan bahwa "tidak dapat bepergian menggunakan kapal". Selain itu, di negara JOI, kapal-kapal baru yang menghubungkan antarpulau mulai beroperasi satu demi satu, dan informasi tersebut disampaikan kepada Anda dari waktu ke waktu. Saat membalas pelanggan, Anda harus memperhatikan informasi terbaru.

Ketika formulir pemesanan pelanggan dan informasi operasional kapal yang baru mulai beroperasi diberikan sebagai masukan, buatlah program untuk menentukan balasan kepada pelanggan.

Format Masukan

Pada baris ke-$1$ masukan tertulis $2$ bilangan bulat $n, k$ ($1 \le n \le 100, 1 \le k \le 5000$). Ini menyatakan bahwa jumlah pulau adalah $n$ pulau dan masukan terdiri dari $k + 1$ baris. Pada baris ke-$(i + 1)$ ($1 \le i \le k$), tertulis $3$ atau $4$ bilangan bulat yang dipisahkan oleh spasi.

• Ketika angka pertama adalah $0$, baris ini menyatakan formulir pemesanan pelanggan. Pada baris ini tertulis $3$ bilangan bulat $0, a, b$ ($1 \le a \le n, 1 \le b \le n, a \ne b$) yang dipisahkan oleh spasi. Ini berarti pelanggan mengirimkan formulir pemesanan dengan pulau $a$ sebagai tempat keberangkatan dan pulau $b$ sebagai tempat tujuan.
• Ketika angka pertama adalah $1$, baris ini menyatakan informasi operasional kapal yang baru mulai beroperasi. Pada baris ini tertulis $4$ bilangan bulat $1, c, d, e$ ($1 \le c \le n, 1 \le d \le n, c \ne d, 1 \le e \le 1000000$). Ini berarti kapal yang melayani perjalanan pulang-pergi antara pulau $c$ dan pulau $d$ baru mulai beroperasi, dan ongkos kapal ini dari pulau $c$ ke pulau $d$ maupun dari pulau $d$ ke pulau $c$ keduanya adalah $e$. Untuk formulir pemesanan setelah baris ini, Anda harus membalas dengan mempertimbangkan kapal ini juga.

Pada tahap awal, dianggap ada $0$ kapal yang beroperasi. Di antara baris masukan, banyaknya baris yang menyatakan informasi operasional kapal paling banyak adalah $1000$ baris. Selain itu, perhatikan bahwa di antara dua pulau yang sama bisa terdapat beberapa kapal yang beroperasi.

Format Keluaran

Misalkan banyaknya baris yang menyatakan formulir pemesanan dalam masukan adalah $m$. Keluaran terdiri dari $m$ baris, dan pada baris ke-$i$ ($1 \le i \le m$), tuliskan sebuah bilangan bulat yang menyatakan balasan untuk formulir pemesanan ke-$i$. Artinya, jika memungkinkan untuk bepergian antara tempat keberangkatan dan tempat tujuan pada formulir pemesanan ke-$i$ dengan berpindah-pindah beberapa kapal, tuliskan nilai minimum dari total ongkosnya. Jika tidak memungkinkan untuk bepergian, tuliskan $-1$.

Contoh Masukan dan Keluaran

Contoh Masukan 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

Contoh Keluaran 1

-1
15
12

Contoh Masukan 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

Contoh Keluaran 2

5955
21431
9298
16392
24774
8840