Nước JOI có \(n\) hòn đảo được đánh số từ \(1\) đến \(n\). Bạn làm việc tại trung tâm bán vé tàu. Khách hàng lần lượt gửi yêu cầu đi từ một đảo đến một đảo khác với tổng giá vé nhỏ nhất; họ có thể đổi tàu nhiều lần. Nếu không thể đi bằng tàu thì phải báo rằng không có hành trình phù hợp.

Các tuyến tàu mới liên tục được mở. Hãy xử lý các thông tin và yêu cầu theo đúng thứ tự nhận được, dùng tất cả các tuyến đã được thông báo trước thời điểm mỗi yêu cầu.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa \(n,k\) với \(1 \le n \le 100\), \(1 \le k \le 5000\).

Mỗi dòng trong \(k\) dòng tiếp theo có một trong hai dạng:

• 0 a b: yêu cầu tìm giá vé nhỏ nhất từ đảo \(a\) đến đảo \(b\), với \(1 \le a,b \le n\), \(a \ne b\).
• 1 c d e: mở một tuyến tàu hai chiều giữa \(c\) và \(d\), giá vé mỗi chiều là \(e\), với \(1 \le c,d \le n\), \(c \ne d\), \(1 \le e \le 1000000\).

Ban đầu không có tuyến tàu nào. Có không quá \(1000\) dòng thông báo mở tuyến. Có thể có nhiều tuyến tàu giữa cùng một cặp đảo.

Dữ liệu ra

Ghi ra đầu ra chuẩn.

Với mỗi yêu cầu loại 0, ghi một dòng chứa tổng giá vé nhỏ nhất, hoặc \(-1\) nếu không thể đến đích. Các câu trả lời phải theo thứ tự yêu cầu. Nếu có \(m\) yêu cầu thì đầu ra có \(m\) dòng.

Chấm điểm

Có \(5\) bộ dữ liệu, mỗi bộ \(4\) điểm; tổng cộng \(20\) điểm.

Ví dụ

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
15
12

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

5955
21431
9298
16392
24774
8840