def solve():

    max_fare = 99000001

    def dijkstra(start, goal):

        unvisited = [i for i in range(n)]

        fare = [max_fare] * n

        fare[start] = 0

        

        while True:

            min_fare = max_fare

            for i in unvisited:

                f = fare[i]

                if f < min_fare:

                    min_fare = f

                    u = i

                    

            if u == goal:

                return min_fare

            elif min_fare == max_fare:

                return -1

            

            unvisited.remove(u)

            

            for v, f in adj[u]:

                if v in unvisited:

                    fare[v] = min(min_fare + f, fare[v])

        

    import sys

    file_input = sys.stdin

    

    while True:

        n, k = list(map(int, file_input.readline().split()))

        if n == 0 and k == 0:

            break

        

        adj = [[] for i in range(n)]

        

        for i in range(k):

            line = file_input.readline()

            if line[0] == '0':

                a, b = list(map(int, line[2:].split()))

                print((dijkstra(a - 1, b - 1)))

            else:

                c, d, e = list(map(int, line[2:].split()))

                adj[c - 1].append((d - 1, e))

                adj[d - 1].append((c - 1, e))



solve()

def solve():

    from heapq import heappush, heappop

    def dijkstra(start, goal):

        fare = [99000001] * n

        fare[start] = 0

        pq = [(0, start)]

        

        while pq:

            u_fare, u = heappop(pq)

                    

            if u == goal:

                return u_fare

            

            for f, v in adj[u]:

                new_fare = u_fare + f

                if new_fare < fare[v]:

                    fare[v] = new_fare

                    heappush(pq, (new_fare, v))

        return -1

        

    import sys

    file_input = sys.stdin

    

    while True:

        n, k = list(map(int, file_input.readline().split()))

        if n == 0 and k == 0:

            break

        

        adj = [[] for i in range(n)]

        

        for i in range(k):

            line = file_input.readline()

            if line[0] == '0':

                a, b = list(map(int, line[2:].split()))

                print((dijkstra(a - 1, b - 1)))

            else:

                c, d, e = list(map(int, line[2:].split()))

                adj[c - 1].append((e, d - 1))

                adj[d - 1].append((e, c - 1))



solve()

def solve():
    max_fare = 99000001

    def dijkstra(start, goal):
        unvisited = [i for i in range(n)]
        fare = [max_fare] * n
        fare[start] = 0
        while True:
            min_fare = max_fare
            for i in unvisited:
                f = fare[i]
                if f < min_fare:
                    min_fare = f
                    u = i
            if u == goal:
                return min_fare
            elif min_fare == max_fare:
                return -1
            unvisited.remove(u)
            for v, f in adj[u]:
                if v in unvisited:
                    fare[v] = min(min_fare + f, fare[v])

    import sys

    file_input = sys.stdin
    while True:
        n, k = list(map(int, file_input.readline().split()))
        if n == 0 and k == 0:
            break
        adj = [[] for i in range(n)]
        for i in range(k):
            line = file_input.readline()
            if line[0] == "0":
                a, b = list(map(int, line[2:].split()))
                print((dijkstra(a - 1, b - 1)))
            else:
                c, d, e = list(map(int, line[2:].split()))
                adj[c - 1].append((d - 1, e))
                adj[d - 1].append((c - 1, e))


solve()

def solve():
    from heapq import heappush, heappop

    def dijkstra(start, goal):
        fare = [99000001] * n
        fare[start] = 0
        pq = [(0, start)]
        while pq:
            u_fare, u = heappop(pq)
            if u == goal:
                return u_fare
            for f, v in adj[u]:
                new_fare = u_fare + f
                if new_fare < fare[v]:
                    fare[v] = new_fare
                    heappush(pq, (new_fare, v))
        return -1

    import sys

    file_input = sys.stdin
    while True:
        n, k = list(map(int, file_input.readline().split()))
        if n == 0 and k == 0:
            break
        adj = [[] for i in range(n)]
        for i in range(k):
            line = file_input.readline()
            if line[0] == "0":
                a, b = list(map(int, line[2:].split()))
                print((dijkstra(a - 1, b - 1)))
            else:
                c, d, e = list(map(int, line[2:].split()))
                adj[c - 1].append((e, d - 1))
                adj[d - 1].append((e, c - 1))


solve()

-    max_fare = 99000001 +    from heapq import heappush, heappop -        unvisited = [i for i in range(n)] -        fare = [max_fare] * n +        fare = [99000001] * n -        while True: -            min_fare = max_fare -            for i in unvisited: -                f = fare[i] -                if f < min_fare: -                    min_fare = f -                    u = i +        pq = [(0, start)] +        while pq: +            u_fare, u = heappop(pq) -                return min_fare -            elif min_fare == max_fare: -                return -1 -            unvisited.remove(u) -            for v, f in adj[u]: -                if v in unvisited: -                    fare[v] = min(min_fare + f, fare[v]) +                return u_fare +            for f, v in adj[u]: +                new_fare = u_fare + f +                if new_fare < fare[v]: +                    fare[v] = new_fare +                    heappush(pq, (new_fare, v)) +        return -1 -                adj[c - 1].append((d - 1, e)) -                adj[d - 1].append((c - 1, e)) +                adj[c - 1].append((e, d - 1)) +                adj[d - 1].append((e, c - 1))