Cacher is the code snippet organizer for pro developers

constexpr LL kInf = 1e18;
typedef pair<LL, int> P;  // cost, vertex_idx
struct Edge {
  int to;
  LL cost;
  Edge(int a, LL b) : to(a), cost(b) {}
};

vector<LL> dijkstra(int s, const vector<vector<Edge>>& G) {
  priority_queue<P, vector<P>, greater<P>> que;

  vector<LL> d(G.size(), kInf);
  d[s] = 0;
  que.push(P(0, s));

  while (!que.empty()) {
    auto p = que.top(); que.pop();
    LL dist = p.first;
    int v = p.second;

    if (d[v] < dist) continue;
    for (const auto& e : G[v]) {
      if (d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        que.push(P(d[e.to], e.to));
      }
    }
  }

  return d;
}

int main() {
  int V, E, s; cin >> V >> E >> s;
  G.resize(V);

  for (int i = 0; i < E; ++i) {
    int s, t, w; cin >> s >> t >> w;
    G[s].push_back(Edge(t, w));
  }

  auto d = dijkstra(s, G);

  for (int i = 0; i < V; ++i) cout << d[i] << endl;
}