Buggy python submission (verdict: Time Limit Exceeded):
#elst...i->j = elst[i]j[]
#vlst...[mincost, ...]
INF = 1000000000

def dyc(n,elst,start,goal):
  vlst = [INF for i in range(n)]
  ulst = [0 for i in range(n)]
  vlst[start] = 0
  while True:
    v = -1
    for i in range(n):
      if(ulst[i] == 0 and (v == -1 or vlst[i] < vlst[v])):
        v = i
    if v == -1:
      break
    ulst[v] = 1
    for i in range(n):
      vlst[i] = min(vlst[i], vlst[v] + elst[v][i])
  if vlst[goal] >= INF:
    print(-1)
  else:
    print(vlst[goal])
  
while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    elst = [[INF for i in range(n)] for j in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dyc(n, elst, lst[1] - 1, lst[2] - 1)
      elif lst[0] == 1:
        elst[lst[1] - 1][lst[2] - 1] = min(lst[3],elst[lst[1] - 1][lst[2] - 1])
        elst[lst[2] - 1][lst[1] - 1] = min(lst[3],elst[lst[2] - 1][lst[1] - 1])
  except EOFError:
    break


Fixed submission:
from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break

Buggy python submission (verdict: Time Limit Exceeded):
INF = 1000000000

while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    vlst = [[INF if i != j else 0 for i in range(n)] for j in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        if vlst[lst[1] - 1][lst[2] - 1] >= INF:
          print(-1)
        else:
          print(vlst[lst[1] - 1][lst[2] - 1])
      elif lst[0] == 1:
        for i in range(n):
          for j in range(n):
            vlst[i][j] = min(vlst[i][j],vlst[i][lst[1] - 1] + lst[3] + vlst[lst[2] - 1][j])
            vlst[j][i] = vlst[i][j]
  except EOFError:
    break


Fixed submission:
from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break

Buggy python submission (verdict: Time Limit Exceeded):
INF = 1000000000

while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    D = [[INF if i != j else 0 for i in range(n)] for j in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        a = min(lst[1],lst[2])
        b = max(lst[1],lst[2])
        if D[a - 1][b - 1] >= INF:
          print(-1)
        else:
          print(D[lst[1] - 1][lst[2] - 1])
      elif lst[0] == 1:
        a = min(lst[1],lst[2])
        b = max(lst[1],lst[2])
        for i in range(n):
          for j in range(i,n):
            D[i][j] = min(D[i][j],D[i][a - 1] + lst[3] + D[b - 1][j])
  except EOFError:
    break


Fixed submission:
from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break

Buggy python submission (verdict: Time Limit Exceeded):
INF = 1000000000

while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    D = [[INF if i != j else 0 for i in range(j + 1)] for j in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        a = min(lst[1],lst[2])
        b = max(lst[1],lst[2])
        if D[b - 1][a - 1] >= INF:
          print(-1)
        else:
          print(D[b - 1][a - 1])
      elif lst[0] == 1:
        a = min(lst[1],lst[2])
        b = max(lst[1],lst[2])
        D[b-1][a-1] = min(D[b-1][a-1],lst[3])
        for i in range(n):
          for j in range(0,i + 1):
            D[i][j] = min(D[i][j],D[max(i,a-1)][min(i,a-1)] + lst[3] + D[max(j,b-1)][min(j,b-1)],D[max(i,b-1)][min(i,b-1)] + lst[3] + D[max(j,a-1)][min(j,a-1)])
  except EOFError:
    break


Fixed submission:
from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break

Buggy python submission (verdict: Time Limit Exceeded):
INF = 1000000000

def solve(s,g,E,n):
  D = [INF for i in range(n)]
  D[s] = 0
  V = [(s,0)]
  U = [0 for i in range(n)]
  while V:
    v = V.pop(0)
    U[v[0]] = 1
    for e in E[v[0]]:
      if U[e[0]] == 0 and D[v[0]] + e[1] < D[e[0]]:
        D[e[0]] = D[v[0]] + e[1]
        V.append((e[0],D[e[0]]))
        V = sorted(V,key=lambda x:x[1])
  if D[g] >= INF:
    print(-1)
  else:
    print(D[g])

while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    E = [[] for i in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        solve(lst[1] - 1, lst[2] - 1, E, n)
      elif lst[0] == 1:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])
  except EOFError:
    break


Fixed submission:
from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break

Buggy python submission (verdict: Time Limit Exceeded):
INF = 1000000000

def solve(s,g,E,n):
  D = [INF for i in range(n)]
  D[s] = 0
  V = [(0,s)]
  U = [0 for i in range(n)]
  while V:
    v = V.pop(0)
    U[v[1]] = 1
    for e in E[v[1]]:
      if U[e[0]] == 0 and D[v[1]] + e[1] < D[e[0]]:
        D[e[0]] = D[v[1]] + e[1]
        V.append((D[e[0]],e[0]))
        V.sort()
  if D[g] >= INF:
    print(-1)
  else:
    print(D[g])

while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    E = [[] for i in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        solve(lst[1] - 1, lst[2] - 1, E, n)
      elif lst[0] == 1:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])
  except EOFError:
    break


Fixed submission:
from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break

Buggy python submission (verdict: Time Limit Exceeded):
INF = 1000000000

def solve(s,g,E,n):
  D = [INF for i in range(n)]
  D[s] = 0
  V = [(0,s)]
  while V:
    v = V.pop(0)
    for e in E[v[1]]:
      if D[v[1]] + e[1] < D[e[0]]:
        D[e[0]] = D[v[1]] + e[1]
        V.append((D[e[0]],e[0]))
        V.sort()
  if D[g] >= INF:
    print(-1)
  else:
    print(D[g])
  
while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    E = [[] for i in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        solve(lst[1] - 1, lst[2] - 1, E, n)
      elif lst[0] == 1:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])
  except EOFError:
    break


Fixed submission:
from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break

Buggy python submission (verdict: Time Limit Exceeded):
INF = 1000000000

def solve(s,g,E,n):
  D = [INF for i in range(n)]
  D[s] = 0
  V = [s]
  while V:
    v = V.pop(0)
    for e in E[v]:
      if D[v] + e[1] < D[e[0]]:
        D[e[0]] = D[v] + e[1]
        V.append(e[0])
  if D[g] >= INF:
    print(-1)
  else:
    print(D[g])
  
  
while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    E = [[] for i in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      a = min(lst[1],lst[2])
      b = max(lst[1],lst[2])
      if lst[0] == 0:
        solve(a - 1, b - 1, E, n)
      elif lst[0] == 1:
        E[a - 1].append([b - 1, lst[3]])
        E[b - 1].append([a - 1, lst[3]])
  except EOFError:
    break


Fixed submission:
from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break

Buggy python submission (verdict: Time Limit Exceeded):
INF = 1000000000
def solve(s,g,E,n):
  D = [INF for i in range(n)]
  D[s] = 0
  U = [0 for i in range(n)]
  V = [s]
  while V:
    v = V.pop(0)
    U[v] = 1
    if v == g:
      break
    for e in E[v]:
      if U[e[0]] == 0 and D[v] + e[1] < D[e[0]]:
        D[e[0]] = D[v] + e[1]
        V.append(e[0])
    V = sorted(V,key=lambda x:D[x])
  if D[g] >= INF:
    print(-1)
  else:
    print(D[g])
  
  
while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    E = [[] for i in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      a = min(lst[1],lst[2])
      b = max(lst[1],lst[2])
      if lst[0] == 0:
        solve(a - 1, b - 1, E, n)
      elif lst[0] == 1:
        E[a - 1].append([b - 1, lst[3]])
        E[b - 1].append([a - 1, lst[3]])
  except EOFError:
    break


Fixed submission:
from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break

Buggy python submission (verdict: Time Limit Exceeded):
INF = 1000000000

def solve(s,g,E,n):
  D = [0 if i == s else INF for i in range(n)]
  U = [0 for i in range(n)]
  V = [s]
  while V:
    v = V.pop(0)
    U[v] = 1
    if v == g:
      break
    for e in E[v]:
      if not U[e[0]] and D[v] + e[1] < D[e[0]]:
        D[e[0]] = D[v] + e[1]
        V.append(e[0])
    V = sorted(V,key=lambda x:D[x])
  if D[g] >= INF:
    print(-1)
  else:
    print(D[g])
  
  
while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    E = [[] for i in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      a = min(lst[1],lst[2])
      b = max(lst[1],lst[2])
      if lst[0] == 0:
        solve(a - 1, b - 1, E, n)
      elif lst[0] == 1:
        E[a - 1].append([b - 1, lst[3]])
        E[b - 1].append([a - 1, lst[3]])
  except EOFError:
    break


Fixed submission:
from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break

Buggy python submission (verdict: Runtime Error):
INF = 1000000000

def solve(s,g,E,n):
  D = [0 if i == s else INF for i in range(n)]
  U = [0 for i in range(n)]
  V = [s]
  while V:
    v = V.pop(0)
    if v == g:
      break
    for e in E[v]:
      if and D[v] + e[1] < D[e[0]]:
        D[e[0]] = D[v] + e[1]
        V.append(e[0])
    V = sorted(V,key=lambda x:D[x])
  if D[g] >= INF:
    print(-1)
  else:
    print(D[g])
  
  
while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    E = [[] for i in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      a = min(lst[1],lst[2])
      b = max(lst[1],lst[2])
      if lst[0] == 0:
        solve(a - 1, b - 1, E, n)
      elif lst[0] == 1:
        E[a - 1].append([b - 1, lst[3]])
        E[b - 1].append([a - 1, lst[3]])
  except EOFError:
    break


Fixed submission:
from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break

Buggy python submission (verdict: Time Limit Exceeded):
INF = 1000000000

def solve(s,g,E,n):
  D = [0 if i == s else INF for i in range(n)]
  U = [0 for i in range(n)]
  V = [s]
  while V:
    v = V.pop(0)
    if v == g:
      break
    for e in E[v]:
      if D[v] + e[1] < D[e[0]]:
        D[e[0]] = D[v] + e[1]
        V.append(e[0])
    V = sorted(V,key=lambda x:D[x])
  if D[g] >= INF:
    print(-1)
  else:
    print(D[g])
  
  
while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    E = [[] for i in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      a = min(lst[1],lst[2])
      b = max(lst[1],lst[2])
      if lst[0] == 0:
        solve(a - 1, b - 1, E, n)
      elif lst[0] == 1:
        E[a - 1].append([b - 1, lst[3]])
        E[b - 1].append([a - 1, lst[3]])
  except EOFError:
    break


Fixed submission:
from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break

Buggy python submission (verdict: Time Limit Exceeded):
INF = 1000000000

while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    D = [[0 if i == j else INF for i in range(n)] for j in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        ans = D[lst[1] - 1][lst[2] - 1]
        if ans >= INF:
          print(-1)
        else:
          print(ans)
      elif lst[0] == 1:
        _,a,b,c = lst
        for i in range(n):
          for j in range(n):
            D[i][j] = min(D[i][j], D[i][a - 1] + c + D[b - 1][j], D[i][b - 1] + c + D[a - 1][j])
  except EOFError:
    break


Fixed submission:
from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break

Buggy python submission (verdict: Time Limit Exceeded):
INF = 1000000000

while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    D = [[0 if i == j else INF for i in range(j + 1)] for j in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        a = min(lst[1],lst[2])
        b = max(lst[1],lst[2])
        ans = D[b - 1][a - 1]
        if ans >= INF:
          print(-1)
        else:
          print(ans)
      elif lst[0] == 1:
        _,a,b,c = lst
        for i in range(n):
          for j in range(i):
            D[i][j] = min(D[i][j],
            D[max(i, a - 1)][min(i, a - 1)] + c + D[max(j, b - 1)][min(j, b - 1)],
            D[max(i, b - 1)][min(i, b - 1)] + c + D[max(j, a - 1)][min(j, a - 1)])
  except EOFError:
    break


Fixed submission:
from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break

Buggy python submission (verdict: Time Limit Exceeded):
INF = 1000000000

while True:
  try:
    n,k = list(map(int,input().split()))
    if n == 0 and k == 0:
      break
    D = [[0 if i == j else INF for i in range(n)] for j in range(n)]
    for i in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        ans = D[lst[1] - 1][lst[2] - 1]
        if ans >= INF:
          print(-1)
        else:
          print(ans)
      elif lst[0] == 1:
        _,a,b,c = lst
        for i in range(n):
          for j in range(i):
            D[i][j] = min(D[i][j],
                          D[i][a - 1] + c + D[b - 1][j],
                          D[i][b - 1] + c + D[a - 1][j])
            D[j][i] = D[i][j]
  except EOFError:
    break


Fixed submission:
from heapq import heappush,heappop

def dij(s,g,E):
  h = []
  U = []
  heappush(h,(0,s))
  while h:
    v = heappop(h)
    if v[1] == g:
      if v[0] >= INF:print(-1)
      else:print(v[0])
      break
    U.append(v[1])
    for e in E[v[1]]:
      if not e[0] in U:
        heappush(h,(v[0] + e[1],e[0]))
  else:print(-1)
INF = 100000000
while True:
  try:
    n,k = map(int,input().split())
    if n == 0 and k == 0: break
    E = [[] for i in range(n)]
    for _ in range(k):
      lst = list(map(int,input().split()))
      if lst[0] == 0:
        dij(lst[1] - 1, lst[2] - 1, E)
      else:
        E[lst[1] - 1].append([lst[2] - 1, lst[3]])
        E[lst[2] - 1].append([lst[1] - 1, lst[3]])

  except EOFError:
    break