# ワーシャルフロイド法

INF = 1000000

loop do
  n,k = gets.split(" ").map(&:to_i)
  break if n == 0 && k == 0
  inputs = Array.new(k) { gets.split(" ").map(&:to_i) }

  d = Array.new(n) { Array.new(n) {INF} }
  0.upto(n-1) {|i| d[i][i] = 0}

  inputs.each do |input|
    if input[0] == 0
      puts d[input[1]-1][input[2]-1]
    else
      # 運賃を更新する
      if d[input[1]-1][input[2]-1] <= input[3]
        next
      else
        d[input[1]-1][input[2]-1] = input[3]
        d[input[2]-1][input[1]-1] = input[3]
      end
      # ここでワーシャルフロイド
      for i in 0...n do
        for j in 0...n do
          for k in 0...n do
            d[i][k] = [d[i][k],d[i][j]+d[j][k]].min
          end
        end
      end
    end
  end
end