西伯利亚北部的寒地，坐落着由 N 个小岛组成的岛屿群，我们把这些小岛依次编号为 1 到 N 。

起初，岛屿之间没有任何的航线。后来随着交通的发展，逐渐出现了一些连通两座小岛的航线。
例如增加一条在 u 号小岛与 v 号小岛之间的航线，这条航线的用时为 e。 那么沿着这条航线，u 号小岛上的人可以前往 v 号小岛，同样的 v 号小岛上的人也可以前往 u 号小岛，其中沿着这一条航线花费的时间为 e。

同时，随着旅游业的发展，越来越多的人前来游玩。那么两个小岛之间的最短路径是多少便成为了饱受关注的话题。

输入格式

输出格式

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

struct na{

    int y,z,ne;

    na(){

        ne=;

    }

};

int n,m,dis[][],c,x,y,z,p,l[],r[],num=,k;

na b[];

char o;

queue <int> q;

bool bo[];

const int INF=1e9;

inline int read(){

    p=;o=getchar();

    while(o<''||o>'') o=getchar();

    while(o>=''&&o<='') p=p*+o-,o=getchar();

    return p;

}

inline void in(int x,int y,int z){

    num++;

    if (l[x]==) l[x]=num;else b[r[x]].ne=num;

    b[num].y=y;b[num].z=z;r[x]=num;

}

int main(){

    n=read();m=read();

    int i,j;

    for (i=;i<=n;i++)

    for (j=;j<=n;j++) dis[i][j]=INF;

    for (i=;i<=n;i++) dis[i][i]=;

    while(m--){

        c=read();x=read();y=read();

        if (c==){

            if (dis[x][y]==INF) printf("-1\n");else printf("%d\n",dis[x][y]);

        }else{

            z=read();

            in(x,y,z);in(y,x,z);

            for (i=;i<=n;i++){

                q.push(x);q.push(y);

                bo[x]=bo[y]=;

                while(!q.empty()){

                    k=q.front();q.pop();

                    bo[k]=;

                    for (j=l[k];j;j=b[j].ne)

                    if (dis[i][b[j].y]>dis[i][k]+b[j].z){

                        dis[i][b[j].y]=dis[i][k]+b[j].z;

                        if (!bo[b[j].y])q.push(b[j].y),bo[b[j].y]=;

                    }

                }

            }

        }

    }

}