船舶が次々と運行を開始していく状況の中で，指定された二点間の現在の最小運賃を計算する問題である．

　現在までの二点間の最小運賃を格納した二次元配列（例えば，二次元配列 fares は，fares[a][b] の中に，島 a から島 b へ向かうときの最小運賃を表す値を格納する）を用いて， 新たに運航を開始した船舶の運航情報を受け取るごとにこの二次元配列を更新し， 客からの注文票にはこの二次元配列を参照し最小運賃を出力する．

二次元配列の初期化
　入力を読み込む前に，船舶が一隻も運航していないときの状態を表した現在までの二点間の最小運賃を表す二次元配列を生成する．
　二次元配列の添え字が i == i のときは，同じ島であるので一隻も船舶に乗らずに島 i から島 i へ移動できるため 0 を格納する．
　その他のときは，船舶は一隻も運行を開始していないので，別の島に移動することができないため，移動できないことを表した十分に大きな値を格納する． この十分に大きな値とは，（運賃の最大値×島数）よりも十分に大きく， ３倍してもオーバーフローしない程度に小さい値とする．十分に大きな値にこのような上限を設けるのは，以下で述べる現在までの二点間の最小運賃を格納した二次元配列を更新する際に，オーバーフローを起こさないようにするためである． また，もしこの十分に大きな値が最小運賃となった場合， 島 a から島 b へ向かう航路が存在しないものとし，出力するときは -1 を出力する．

各入力に対する処理
新たに運航を開始した船舶の運航情報の場合
　新たに運航を開始した船舶の運賃が，その船舶が運航する島 a と島 b を結ぶ航路の最小運賃（現在までの二点間の最小運賃を格納した二次元配列に格納されている値）と比較して，以下のように，高い場合，等しい場合，安い場合に場合分けをして考えると，安い場合のみ現在までの二点間の最小運賃を格納した二次元配列を更新すれば良いことが分かる．

• 島 a と島 b を結ぶ航路の最小運賃よりも高い場合，
  島 a と島 b の間を移動するときはより安価な航路が存在し，島 a と島 b の間を経由するような航路の場合もより安価な航路を使えばよいので，最小運賃にこの運行情報は影響を与えない．
• 島 a と島 b を結ぶ航路の最小運賃と等しい場合，
  島 a と島 b の間を移動するときは同一価格の航路がすでに存在し，島 a と島 b の間を経由するような航路の場合も最小運賃は変わらないため，最小運賃にこの運行情報は新たな影響を与えない．
• 島 a と島 b を結ぶ航路の最小運賃よりも安い場合，
  少なくとも島 a と島 b の間を移動するときはこの新たに運行を開始した船舶に乗船することがもっとも安価な移動方法である．また，ある島 c からある島 d へ移動する場合も，この船舶を経由して移動することがもっとも安価となる場合もある．以下のように，新たに運行を開始した船舶に乗船した場合の最小運賃の二通りと乗船しなかった場合の最小運賃の合計三通りに場合分けをして，その中の最小値を計算することによって，新たに一件の運行情報を受け取った場合の二点間の現在までの最小運賃を，計算することができる．
  • 出発地から島 a まで最小運賃で向かい， 新たに運航を開始した船舶に乗船し島 a から島 b へ向かい， 島 b から目的地まで最小運賃で向かう場合の合計運賃．
  • 出発地から島 b まで最小運賃で向かい， 新たに運航を開始した船舶に乗船し島 b から島 a に向かい， 島 a から目的地まで最小運賃で向かう場合の合計運賃．
  • 新たに運航を開始した船舶を使わず，目的地から出発地へ向かう場合の最小運賃． つまり，更新前の現在までの二点間の最小運賃を保存している二次元配列に格納されている値．
  二点間の現在までの最小運賃を格納した二次元配列の出発地と目的地の任意の組み合わせは，以上の三通りの中の最小値 に更新すればよい．

　また，新たに運行を開始した船舶の運行情報一件あたりの現在までの二点間の最小運賃を保存している二次元配列を更新するための計算量は，島の数を n とおくと，O(n²) である．

客からの注文票の場合
　現在までの二点間の最小運賃を格納している二次元配列を参照し，出力する．
　二次元配列に格納されている島 a から島 b への最小運賃の値が十分に大きな数であった場合，島 a から島 b に移動する航路が存在していないことを表しているため，-1 を出力する．それ以外の場合は，この二次元配列に格納されている値を出力する．
　よって，出力に要する計算量は O(1) である．

　以上から，全体の計算量は，船舶の運航開始情報の数をkとおくと，O(kn²) である．

別解法
　各島を頂点，船舶を辺，船舶の運賃を辺の重みとした重み付き無向グラフを構築すると，重み付きグラフに対する最短経路を求めるアルゴリズムを使うことによって，この問題を解くことができる．
　最短経路を求めるアルゴリズムには，DijkstraのアルゴリズムやFroid-Worshalのアルゴリズムなどがある．
　Dijkstraのアルゴリズムの場合の計算量は，新たに運航を開始した船舶の運航情報の場合は一件あたり O(1) であり，客からの注文票の場合は一件あたり O((k + n) log n) である．よって，全体の計算量は，客からの注文票の数をmとおくと，O(m (k + n) log n) である．
　Froid-Worshalのアルゴリズムの場合の計算量は，船舶の運行情報一件あたりの計算量は O(n³) であり，客からの注文票で最小運賃を計算する場合は O(1) である．よって，全体の計算量は，O(kn³) である．
　入力データの大きさから三つの解法の中でもっとも時間のかかるFroid-Worshalのアルゴリズムを用いた場合であっても，各入力に対し高々10秒程度プログラムを実行すれば解ける．