# ワーシャルフロイド法っぽい

INF = 100000000

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
      if d[input[1]-1][input[2]-1] == INF
        puts -1
      else
        puts d[input[1]-1][input[2]-1]
      end
    else
      # 運賃を更新する
      a = input[1]-1
      b = input[2]-1
      if d[a][b] <= input[3]
        next
      else
        d[a][b] = input[3]
        d[b][a] = input[3]
      end
      # ここでワーシャルフロイドっぽい
      for i in 0...n do
        for j in 0...n do
          d[i][j] = [d[i][j],d[i][a]+d[a][b]+d[b][j],d[i][b]+d[b][a]+d[a][j]].min
        end
      end
    end
  end
end