void Dijkstra(int n)
{
    int k,min_dist;
    for(int i=1; i<=n; i++)
    {
        dist[i]=W[1][i];
        vis[i]=0;
    }
    for(int i=1; i<=n; i++)
    {
        k=0;
        min_dist=INF;
        for(int j=1; j<=n; j++)
            if(vis[j]==0&&dist[j]<min_dist)
            {
                min_dist=dist[j];
                k=j;
            }
        vis[k]=1;
        for(int j=1; j<=n; j++)
            if(vis[j]==0&&dist[k]+W[k][j]<dist[j])
                dist[j]=dist[k]+W[k][j];
    }
}
//Dijkstra + 优先队列 + 前向星

//前向星建图 int dis[1005]; bool book[1005];

struct Point
{
    int dis, x;
    Point(int a = 0, int b = 0): x(a), dis(b) {} friend bool operator <(Point a, Point b)
    {
        return a.dis > b.dis;
    }
};
int dij(int u, int En)
{
    memset(book,false,sizeof(book));
    memset(dis,0x3f,sizeof(dis));
    dis[u] = 0;
    priority_queue<Point> q;
    q.push(Point(u,0));
    Point st;
    while(!q.empty())
    {
        st = q.top();
        q.pop();
        if(book[st.x]) continue;
        book[st.x] = 1;
        for(int i = first[st.x]; ~i; i = e[i].next)
        {
            if(dis[ e[i].v ] > dis[st.x] + e[i].w)
            {
                dis[ e[i].v ] =dis[st.x] + e[i].w;
                q.push(Point(e[i].v, dis[e[i].v] ) );
            }
        }
    }
    return dis[En];
}

//Dijkstra + 邻接矩阵

#define For(a,b,c) for(int a = b; a <= c; a++) int e[2005][2005], dis[2005], N;
bool book[2005];

/* 建 图 int u, v, w;
memset(e,0x3f,sizeof(e)); For(i,1,N) e[i][i] = 0; while(M--)
{
scanf("%d%d%d",&u,&v,&w); if(e[u][v] > w) e[u][v] = e[v][u] = w;
}
*/

int dij(int u, int En)
{
    memset(book,false,sizeof(book));
    memset(dis,0x3f,sizeof(dis));
    book[u] = true;
    For(i,1,N) dis[i] = e[u][i];

    int minn, k;
    For(i,2,N)
    {
        minn = 0x3f3f3f3f;
        For(j,1,N) if(!book[j] && minn > dis[j]) minn = dis[j], k = j;
        book[k] = true;
        For(j,1,N) if(dis[j] > dis[k] + e[k][j]) dis[j] = dis[k] + e[k][j];
    }
    return dis[En];
}

//邻接矩阵 + 优先队列 + Dijkstra （用处不大,尽量不用）

//只用这个写过一道水题，不保证正确性
//不过，应该没毛病（手动滑稽
//好像也没快多少struct Point
{
    int dis, x;
    Point(int a = 0, int b = 0): x(a), dis(b) {} friend bool operator <(Point a, Point b)
    {
        return a.dis > b.dis;
    }
};

int dij(int u, int En)
{
    memset(book,false,sizeof(book));
    memset(dis,0x3f,sizeof(dis));
    dis[u] = 0;

    priority_queue<Point> q;
    q.push( Point(u,0) );
    Point st;
    while(!q.empty())
    {
        st = q.top();
        q.pop();
        if(book[st.x]) continue;
        book[st.x] = true;
        For(i,1,N)
        {
            if(dis[i] > dis[st.x] + e[st.x][i])
            {
                dis[i] = dis[st.x] + e[st.x][i];
                q.push( Point(i,dis[i]) );
            }
        }
    }
    return dis[En];
}