
import java.util.*

fun main(args:Array<String>):Unit {
    var (n, k) = readLine()!!.split(' ').map(String::toInt)
    while (n != 0) {
        val feeTable = Array(n) {x ->  Array(n) {y -> if (x != y) Int.MAX_VALUE.toLong() else 0L} }
        repeat(k){
            val query = readLine()!!.split(' ').map(String::toInt)
            when(query.first()){
                0 -> {
                    val (_, a, b) = query
                    println(when(feeTable[a - 1][b - 1]){
                        Int.MAX_VALUE.toLong() -> -1
                        else -> feeTable[a - 1][b - 1]
                    })
                }
                1 -> {
                    val (_, c, d, e) = query
                    for (from in 0 until n){
                        for (to in (from + 1) until n){
                            if (feeTable[from][to] > feeTable[from][c - 1] + feeTable[d - 1][to] + e){
                                feeTable[from][to] = feeTable[from][c - 1] + feeTable[d - 1][to] + e
                                feeTable[to][from] = feeTable[from][to]
                            }
                            if (feeTable[from][to] > feeTable[from][d - 1] + feeTable[c - 1][to] + e){
                                feeTable[from][to] = feeTable[from][d - 1] + feeTable[c - 1][to] + e
                                feeTable[to][from] = feeTable[from][to]
                            }
                        }
                    }
                }
            }
        }
        val (nn, nk) = readLine()!!.split(' ').map(String::toInt)
        n = nn
        k = nk
    }
}
