using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("3 8");
WillReturn.Add("1 3 1 10");
WillReturn.Add("0 2 3");
WillReturn.Add("1 2 3 20");
WillReturn.Add("1 1 2 5");
WillReturn.Add("0 3 2");
WillReturn.Add("1 1 3 7");
WillReturn.Add("1 2 1 9");
WillReturn.Add("0 2 3");
WillReturn.Add("5 16");
WillReturn.Add("1 1 2 343750");
WillReturn.Add("1 1 3 3343");
WillReturn.Add("1 1 4 347392");
WillReturn.Add("1 1 5 5497");
WillReturn.Add("1 2 3 123394");
WillReturn.Add("1 2 4 545492");
WillReturn.Add("1 2 5 458");
WillReturn.Add("1 3 4 343983");
WillReturn.Add("1 3 5 843468");
WillReturn.Add("1 4 5 15934");
WillReturn.Add("0 2 1");
WillReturn.Add("0 4 1");
WillReturn.Add("0 3 2");
WillReturn.Add("0 4 2");
WillReturn.Add("0 4 3");
WillReturn.Add("0 5 3");
WillReturn.Add("0 0");
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
long CurrInd = 0;
while (true) {
SplitAct(InputList[(int)CurrInd]);
long N = wkArr[0];
long M = wkArr[1];
if (N == 0 && M == 0) break;
string[] InputArr = InputList.Skip((int)CurrInd).Take(1 + (int)M).ToArray();
Solve(InputArr);
CurrInd += M + 1;
}
}
static long mN;
struct EdgeInfoDef
{
internal long ToNode;
internal long Cost;
}
static Dictionary<long, List<EdgeInfoDef>> mEdgeInfoListDict = new Dictionary<long, List<EdgeInfoDef>>();
static void Solve(string[] pInputArr)
{
long[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
SplitAct(pInputArr[0]);
mN = wkArr[0];
mEdgeInfoListDict.Clear();
for (long I = 1; I <= mN; I++) {
mEdgeInfoListDict[I] = new List<EdgeInfoDef>();
}
foreach (string EachStr in pInputArr.Skip(1)) {
SplitAct(EachStr);
long Type = wkArr[0];
if (Type == 0) {
long StaNode = wkArr[1];
long GoalNode = wkArr[2];
Dictionary<long, long> Result = Dijkstra(StaNode, GoalNode);
if (Result.ContainsKey(GoalNode)) {
Console.WriteLine(Result[GoalNode]);
}
else {
Console.WriteLine(-1);
}
}
if (Type == 1) {
long FromNode = wkArr[1];
long ToNode = wkArr[2];
long Cost = wkArr[3];
mEdgeInfoListDict[FromNode].Add(new EdgeInfoDef() { ToNode = ToNode, Cost = Cost });
mEdgeInfoListDict[ToNode].Add(new EdgeInfoDef() { ToNode = FromNode, Cost = Cost });
}
}
}
// ダイクストラ法で、各ノードまでの最短距離を求める
static Dictionary<long, long> Dijkstra(long pStaNode, long pGoalNode)
{
var InsPQueue = new PQueue_Arr();
// 距離合計[確定ノード]なDict
var KakuteiNodeDict = new Dictionary<long, long>();
KakuteiNodeDict.Add(pStaNode, 0);
//Enqueue処理
Action<long> EnqueueAct = pFromNode =>
{
if (mEdgeInfoListDict.ContainsKey(pFromNode) == false) {
return;
}
foreach (EdgeInfoDef EachEdge in mEdgeInfoListDict[pFromNode]) {
// 確定ノードならContinue
if (KakuteiNodeDict.ContainsKey(EachEdge.ToNode)) continue;
long wkSumCost = KakuteiNodeDict[pFromNode] + EachEdge.Cost;
PQueue_Arr.PQueueJyoutaiDef WillEnqueue;
WillEnqueue.Node = EachEdge.ToNode;
WillEnqueue.SumCost = wkSumCost;
InsPQueue.Enqueue(WillEnqueue);
}
};
EnqueueAct(pStaNode);
while (InsPQueue.IsEmpty() == false) {
PQueue_Arr.PQueueJyoutaiDef Dequeued = InsPQueue.Dequeue();
// 確定ノードならcontinue
if (KakuteiNodeDict.ContainsKey(Dequeued.Node)) continue;
// 枝切り
if (KakuteiNodeDict.ContainsKey(pGoalNode)) break;
KakuteiNodeDict.Add(Dequeued.Node, Dequeued.SumCost);
EnqueueAct(Dequeued.Node);
}
return KakuteiNodeDict;
}
}
#region PQueue_Arr
// 内部で配列使用の優先度付きキュー
internal class PQueue_Arr
{
internal struct PQueueJyoutaiDef
{
internal long Node;
internal long SumCost;
}
private PQueueJyoutaiDef[] mHeapArr;
private long mHeapArrCnt = 0;
// コンストラクタ
internal PQueue_Arr()
{
mHeapArr = new PQueueJyoutaiDef[65535];
}
internal bool IsEmpty()
{
return mHeapArrCnt == 0;
}
// エンキュー処理
internal void Enqueue(PQueueJyoutaiDef pAddJyoutai)
{
long CurrNode = 1 + mHeapArrCnt;
if (mHeapArr.GetUpperBound(0) < CurrNode) {
ExtendArr();
}
mHeapArr[CurrNode] = pAddJyoutai;
mHeapArrCnt++;
while (1 < CurrNode && mHeapArr[CurrNode / 2].SumCost > mHeapArr[CurrNode].SumCost) {
PQueueJyoutaiDef Swap = mHeapArr[CurrNode];
mHeapArr[CurrNode] = mHeapArr[CurrNode / 2];
mHeapArr[CurrNode / 2] = Swap;
CurrNode /= 2;
}
}
// 配列のExtend
private void ExtendArr()
{
PQueueJyoutaiDef[] NewHeapArr = new PQueueJyoutaiDef[mHeapArrCnt * 2];
mHeapArr.CopyTo(NewHeapArr, 0);
mHeapArr = NewHeapArr;
}
// デキュー処理
internal PQueueJyoutaiDef Dequeue()
{
PQueueJyoutaiDef TopNode = mHeapArr[1];
long LastNode = mHeapArrCnt;
mHeapArr[1] = mHeapArr[LastNode];
mHeapArrCnt--;
MinHeapify(1);
return TopNode;
}
// 根ノードを指定し、根から葉へヒープ構築
private void MinHeapify(long pRootNode)
{
if (mHeapArrCnt <= 1) {
return;
}
long Left = pRootNode * 2;
long Right = pRootNode * 2 + 1;
// 左の子、自分、右の子で値が最小のノードを選ぶ
long Smallest = mHeapArr[pRootNode].SumCost;
long SmallestNode = pRootNode;
if (Left <= mHeapArrCnt && mHeapArr[Left].SumCost < Smallest) {
Smallest = mHeapArr[Left].SumCost;
SmallestNode = Left;
}
if (Right <= mHeapArrCnt && mHeapArr[Right].SumCost < Smallest) {
Smallest = mHeapArr[Right].SumCost;
SmallestNode = Right;
}
// 子ノードのほうが大きい場合
if (SmallestNode != pRootNode) {
PQueueJyoutaiDef Swap = mHeapArr[SmallestNode];
mHeapArr[SmallestNode] = mHeapArr[pRootNode];
mHeapArr[pRootNode] = Swap;
// 再帰的に呼び出し
MinHeapify(SmallestNode);
}
}
}
#endregion