using i64 = long long;
i64 n, m, s;
struct point {
    i64 v, w;
    bool operator<(const point &other) const { return w > other.w; }
};

vector<vector<point>> graph;
vector<i64> dijkstra(const i64 s = 1) {
    vector<i64> map(n + 1, INT32_MAX); //改成INT64_MAX却过不了第三个点，第三个点有个答案就正好是INT32_MAX
    vector<bool> vis(n + 1, false);
    priority_queue<point> q;
    map[s] = 0;
    q.emplace(s, 0);
    while (not q.empty()) {
        point t = q.top();
        q.pop();
        if (vis[t.v])
            continue;
        vis[t.v] = true;
        for (auto &&i : graph[t.v])
            if (map[t.v] + i.w < map[i.v]) {
                map[i.v] = map[t.v] + i.w;
                q.emplace(i.v, map[i.v]);
            }
    }
    map.erase(map.begin());
    return map;
}