template <typename T>
struct edge
{
    int to;
    T cost;
    edge(int t, T c) : to(t), cost(c) {}
};
#define P pair<T, int> //P.first:最短距離,P.second:頂点の番号
//頂点V個の負閉路なし重み付きグラフGにおける始点sからの最短距離を求める
template <typename T>
void dijkstra(vector<vector<edge<T>>> G, vector<T> &dist, int s)
{
    int V = G.size();
    //greater<P>によってfirstが小さい順に取り出される
    priority_queue<P, vector<P>, greater<P>> que;
    for (int i = 0; i < V; i++)
        dist[i] = numeric_limits<T>::max();
    dist[s] = (T)0;
    que.push(P((T)0, s));
    //queが空になるまで繰り返す
    while (!que.empty())
    {
        P p = que.top();
        que.pop();
        int v = p.second;
        if (dist[v] < p.first)
            continue; //すでに最短距離ならスルー
        for (int i = 0; i < G[v].size(); i++)
        {
            edge e = G[v][i];
            //更新作業
            if (dist[e.to] > dist[v] + e.cost)
            {
                dist[e.to] = dist[v] + e.cost;
                que.push(P(dist[e.to], e.to));
            }
        }
    }
}
#undef P