import Control.Monad (foldM_)
import Data.Array (Array,listArray,(!),(//),accum)
import Data.List (delete)

data Cost = Cost Int | Unlimited deriving (Eq,Ord,Show)
type CostArray = Array Int Cost
type CostTable = Array (Int,Int) Cost

main = do
    [n,k] <- getLine >>= return . map read . words
    if all (==0) [n,k] then return () else do
        foldM_ (execute n) (initTable n) [1..k]

        main

    where
    execute n ct _ = do
        ns <- getLine >>= return . map read . words
        case ns of
            [0,a,b] -> do
                print $ lowest n ct a b
                return ct
            [1,a,b,c] -> do
                return (updateTable (a,b) c ct)
        


initTable :: Int -> CostTable
initTable n = listArray ((1,1),(n,n)) (repeat Unlimited)

updateTable :: (Int,Int) -> Int -> CostTable -> CostTable
updateTable (a,b) c ct = accum min ct [((a,b),Cost c),((b,a),Cost c)]

lowest :: Int -> CostTable -> Int -> Int -> Int
lowest n ct s g = case (step csInit [1..n]) ! g of
        Unlimited -> -1
        Cost c -> c

    where
    csInit = (listArray (1,n) (repeat Unlimited)) // [(s,Cost 0)]

    step cs gs = case lowestGoal of
            Nothing -> cs
            Just g -> step (cs %% g) (delete g gs)
        where
        lowestGoal = lowestGoal' gs Nothing Unlimited
            where
            lowestGoal' [] g' _ = g'
            lowestGoal' (g:gs) g' c'
                | cs!g < c' = lowestGoal' gs (Just g) (cs!g)
                | otherwise = lowestGoal' gs g' c'

        cs %% g0 = accum min cs [(g, (cs!g0)<+>(ct!(g0,g))) | g<-gs, g/=g0]

        Unlimited <+> _ = Unlimited
        _ <+> Unlimited = Unlimited
        Cost a <+> Cost b = Cost (a+b)