第７回日本情報オリンピック　予選６

2007年12月16日
情報オリンピック日本委員会

問題

JOI国には，n 島の島があり， 各島には 1 から n までの番号が付けられている． 現在，JOI国では各島の間を結ぶ航路網の整備が進んでいる．

あなたは，船舶の切符を扱っているチケットセンターに勤務している．JOI国には船舶を使って，できる限り安価に， 島と島の間を旅行したいと考えている人が沢山おり， 彼らは，出発地と目的地を注文票に記入して，あなたのところに送ってくる．
あなたの仕事は，客から注文票を受け取ったらすぐに， いくつかの船舶を乗り継いで， 出発地と目的地を結ぶ航路の中で， もっとも安価な運賃を計算し，客に伝えることである．
ただし，旅程によっては，船舶を使って旅行することが出来ない場合もある． そのときは『船舶を使って旅行することが出来ない』と客に伝える必要がある． また，JOI国では，島と島の間を結ぶ新しい船舶が，次々と運航を開始しており， あなたには，その情報が随時伝えられる． 客に返事をする際には，最新の情報に留意しなければならない．

入力として，客の注文票や新たに運航を開始した船舶の運航情報が与えられたときに， 客への返事を求めるプログラムを作成せよ．

なお，入力例１と出力例１に対する実行状況を，図１として図示している．

入力

入力の 1 行目には2つの整数 n, k (1 ≦ n ≦ 100, 1 ≦ k ≦ 5000) が書かれている． これは，島の数が n 島で，入力が k + 1 行からなることを表す．
i + 1 行目 (1 ≦ i ≦ k) には， 3 個または 4 個の整数が空白を区切りとして書かれている．

• 最初の数字が 0 のとき，この行は客の注文票を表す．
  この行には3個の整数 0, a, b (1 ≦ a ≦ n, 1 ≦ b ≦ n, a ≠ b) が空白を区切りとして書かれている．
  これは，客が，島 a を出発地とし島 b を目的地とするような注文票を送ってきたことを表す．
• 最初の数字が 1 のとき，この行は新たに運航を開始した船舶の運航情報を表す．
  この行には 4 個の整数 1, c, d, e (1 ≦ c ≦ n, 1 ≦ d ≦ n, c ≠ d, 1 ≦ e ≦ 1000000) が書かれている．
  これは島 c と島 d を往復する船舶が新たに運航を開始し， この船舶の島 c から島 d への運賃と，島 d から島 c への運賃が，共に e であることを表す．
  この行以降の注文票に対しては，この船舶も考慮して返事をしなければならない．

最初の段階では，船舶は一隻も運航していないものとする． 入力のうち，船舶の運航情報を表す行は 1000 行以下である． また，島と島の間に，複数の船舶が運航することがあることに注意せよ．

出力

入力のうち，注文票を表す行の数を m とおく．
提出する出力ファイルは m 行からなり， i 行目(1 ≦ i ≦ m)には， i 番目の注文票に対する返事を表す整数を書く．
すなわち， i 番目の注文票の出発地と目的地の間を，いくつかの船舶を乗り継いで旅行することが可能ならば， その運賃の合計の最小値を書く． 旅行することが不可能ならば，-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
  

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
   

-1
15
12
   

5955
21431
9298
16392
24774
8840
   

なお，入力例１と出力例１の船舶が運航を開始していく模様と客からの注文票に対する返答を，図１として以下に図示している．

図１. 入力例１と出力例１に対するアニメーションと分解写真

※各入出力例のデータは， 右クリック等によりファイルに保存して利用可能です．

テストデータ