I=float('inf')

for e in iter(input,'0 0'):

 n,k=list(map(int,e.split()))

 F=[[I]*-~n for _ in[0]*-~n]

 for i in range(1,n+1):F[i][i]=0

 for _ in[0]*k:

  f=eval(input());g=list(map(int,f[2:].split()))

  if'0'==f[0]:a,b=g;A=F[a][b];print(([A,-1][A==I]))

  else:

   c,d,e=g

   if e<F[c][d]:

    for i in range(2,n+1):

     for j in range(1,i):

      F[i][j]=min(F[i][j],F[i][c]+e+F[d][j],F[i][d]+e+F[c][j])

    for j in range(2,n+1):

     for i in range(1,j):

      F[i][j]=F[j][i]

I=float('inf')

for e in iter(input,'0 0'):

 n,k=list(map(int,e.split()))

 F=[[I]*-~n for _ in[0]*-~n]

 for i in range(1,n+1):F[i][i]=0

 for _ in[0]*k:

  f=eval(input());g=list(map(int,f[2:].split()))

  if'0'==f[0]:a,b=g;A=F[a][b];print(([A,-1][A==I]))

  else:

   c,d,e=g

   if e<F[c][d]:

    for i in range(2,n+1):

     for j in range(1,i):

      F[i][j]=F[j][i]=min(F[i][j],F[i][c]+e+F[d][j],F[i][d]+e+F[c][j])

I = float("inf")
for e in iter(input, "0 0"):
    n, k = list(map(int, e.split()))
    F = [[I] * -~n for _ in [0] * -~n]
    for i in range(1, n + 1):
        F[i][i] = 0
    for _ in [0] * k:
        f = eval(input())
        g = list(map(int, f[2:].split()))
        if "0" == f[0]:
            a, b = g
            A = F[a][b]
            print(([A, -1][A == I]))
        else:
            c, d, e = g
            if e < F[c][d]:
                for i in range(2, n + 1):
                    for j in range(1, i):
                        F[i][j] = min(
                            F[i][j], F[i][c] + e + F[d][j], F[i][d] + e + F[c][j]
                        )
                for j in range(2, n + 1):
                    for i in range(1, j):
                        F[i][j] = F[j][i]

I = float("inf")
for e in iter(input, "0 0"):
    n, k = list(map(int, e.split()))
    F = [[I] * -~n for _ in [0] * -~n]
    for i in range(1, n + 1):
        F[i][i] = 0
    for _ in [0] * k:
        f = eval(input())
        g = list(map(int, f[2:].split()))
        if "0" == f[0]:
            a, b = g
            A = F[a][b]
            print(([A, -1][A == I]))
        else:
            c, d, e = g
            if e < F[c][d]:
                for i in range(2, n + 1):
                    for j in range(1, i):
                        F[i][j] = F[j][i] = min(
                            F[i][j], F[i][c] + e + F[d][j], F[i][d] + e + F[c][j]
                        )

-                        F[i][j] = min( +                        F[i][j] = F[j][i] = min( -                for j in range(2, n + 1): -                    for i in range(1, j): -                        F[i][j] = F[j][i]