import sys

r=sys.stdin.readline

I=float('inf')

for e in iter(r,'0 0\n'):

 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=r();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])

def s():

 import sys

 r=sys.stdin.readline

 I=float('inf')

 for e in iter(r,'0 0\n'):

  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=r();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])

if'__main__'==__name__:s()

import sys

r = sys.stdin.readline
I = float("inf")
for e in iter(r, "0 0\n"):
    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 = r()
        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]
                        )

def s():
    import sys

    r = sys.stdin.readline
    I = float("inf")
    for e in iter(r, "0 0\n"):
        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 = r()
            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]
                            )


if "__main__" == __name__:
    s()

-import sys +def s(): +    import sys -r = sys.stdin.readline -I = float("inf") -for e in iter(r, "0 0\n"): -    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 = r() -        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] -                        ) +    r = sys.stdin.readline +    I = float("inf") +    for e in iter(r, "0 0\n"): +        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 = r() +            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] +                            ) + + +if "__main__" == __name__: +    s()