struct ShortestPath
{
    typedef int type;
    static const int inf=1e9;
    static const int __=100005;

    struct edge
    {
        int nex;type dis;
        edge() {}
        edge(int x,type y):
            nex(x),dis(y) {}
        bool operator<(const edge& b)const
        {
            return dis>b.dis;
        }
    };

    int n;
    type dis[__];
    bool vis[__];
    vector<edge>G[__];
    priority_queue<edge>Q;

    type& operator[](int x){return dis[x];}

    void init(int _n)
    {
        n=_n;
        for(int i=1;i<=n;++i)
        {
            vis[i]=false;
            dis[i]=inf;
        }
    }

    void add_edge(int x,int y,type dis)
    {
        G[x].push_back(edge(y,dis));
    }

    //先調(diào)用init
    void Dijkstra(int st)
    {
        dis[st]=0,Q.push(edge(st,0));
        while(!Q.empty())
        {
            int t=Q.top().nex;Q.pop();
            if(vis[t])continue;
            vis[t]=true;
            for(edge &x:G[t])
                if(!vis[x.nex] && dis[t]+x.dis<dis[x.nex])
                {
                    dis[x.nex]=dis[t]+x.dis;
                    Q.push(edge(x.nex,dis[x.nex]));
                }
        }
    }
    void clear()
    {
        for(int i=1;i<=n;++i)
            G[i].clear();
    }
}D;