//
// Created by user on 10/12/17.
//

#ifndef GRAPH_GRAPH_H
#define GRAPH_GRAPH_H

#include <memory>
#include <vector>

class Vertex;
class Edge;

using spVertex = std::shared_ptr<Vertex>;
using wpVertex = std::weak_ptr<Vertex>;
using spEdge = std::shared_ptr<Edge>;
using wpEdge = std::weak_ptr<Edge>;

class Vertex {
    friend class Graph;
    friend class Edge;

    bool _is_removed;
    void add_edge(const spEdge &e);
    int _deg;

public:
    explicit Vertex(int id);
    spEdge head;
    int id;
    int deg() const;
    int deg();
    bool is_alive() const;
    bool is_removed() const;
    void remove();
};

class Edge {
    friend class Graph;
    friend class Vertex;
    Edge();
    wpEdge prev;

public:
    int s, t, c;
    int id;
    wpEdge reverse;
    spEdge next;

    Edge(int s, int t, int c, int id);
    void remove();
};

class Graph {
    friend class Edge;
    friend class Vertex;

    int _size;
    int next_vertex_id;
    int next_edge_id;
    std::vector<spVertex> vertices;
    spEdge add_uniedge(int s, int t, int c, int id);

public:
    Graph();
    explicit Graph(int n);

    int add_vertex();
    std::pair<spEdge, spEdge> add_biedge(int s, int t, int c);
    spEdge add_uniedge(int s, int t, int c);

    int size() const;
    int size();

    void simplify();
    void show() const;

    spVertex operator [] (size_t vid) const;
    spVertex operator [] (size_t vid);
};


#endif //GRAPH_GRAPH_H

//
// Created by user on 10/12/17.
//

//#include "Graph.h"
#include <cassert>
#include <iostream>

using namespace std;

Graph::Graph() : Graph(0) {

}

Graph::Graph(int n) : _size(0), next_vertex_id(0), next_edge_id(0) {
    for (int i = 0; i < n; ++i) {
        add_vertex();
    }
}

int Graph::add_vertex() {
    int id = next_vertex_id++;
    vertices.emplace_back(new Vertex(id));
    return id;
}

std::pair<spEdge, spEdge> Graph::add_biedge(int s, int t, int c) {
    spVertex vs = vertices[s];
    spVertex vt = vertices[t];
    assert(vs->is_alive());
    assert(vt->is_alive());

    spEdge st = add_uniedge(s, t, c, next_edge_id);
    spEdge ts = add_uniedge(t, s, c, next_edge_id);
    st->reverse = ts;
    ts->reverse = st;

    return {st, ts};
}

spEdge Graph::add_uniedge(int s, int t, int c, int id) {
    spEdge st = add_uniedge(s, t, c);
    st->id = id;
    return st;
}

spEdge Graph::add_uniedge(int s, int t, int c) {
    spVertex vs = vertices[s];
    spVertex vt = vertices[t];
    assert(vs->is_alive());
    assert(vs->is_alive());

    spEdge st = make_shared<Edge>(s, t, c, next_edge_id++);
    vs->add_edge(st);

    return st;
}

void Graph::simplify() {
    vector<int> stack;
    for (auto &u : vertices) {
        if (u->is_alive()) {
            if (u->deg() == 1) {
                stack.emplace_back(u->id);
            } else if (u->deg() == 2) {
                stack.emplace_back(u->id);
            }
        }
    }

    while (stack.size() > 0) {
        int u = stack.back();
        stack.pop_back();
        if (vertices[u]->is_removed()) {
            continue;
        }

    }
}

int Graph::size() const {
    // TODO: alert that this takes O(n)
    int res = 0;
    for (const auto &u : vertices) {
        if (u->is_alive()) ++res;
    }
    return res;
}

spVertex Graph::operator[](size_t vid) const {
    return vertices[vid];
}

spVertex Graph::operator[](size_t vid) {
    return vertices[vid];
}

int Graph::size() {
    return const_cast<Graph*>(this)->size();
}

void Graph::show() const {
    for (const spVertex &v : vertices) {
        if (v->is_alive()) {
            for (spEdge e = v->head; e; e = e->next) {
                cout << e->s << "->" << e->t << endl;
            }
        }
    }
}

Vertex::Vertex(int id) : id(id), head(), _is_removed(false) {
}

bool Vertex::is_alive() const {
    return !_is_removed;
}

void Vertex::add_edge(const spEdge &e) {
    e->next = head;
    head = e;
    if (e->next) {
        e->prev = head;
    }
    head->prev.reset();
    ++_deg;
}

int Vertex::deg() const {
    return _deg;
}

int Vertex::deg() {
    return _deg;
}

bool Vertex::is_removed() const {
    return !is_alive();
}

void Vertex::remove() {
    while (head) {
        head->remove();
    }
}

Edge::Edge() : Edge(-1, -1, -1, -1) {
}

Edge::Edge(int s, int t, int c, int id)
        : s(s), t(t), c(c), id(id), reverse(), next() {
}

void Edge::remove() {
    if (prev.lock()) {
        prev.lock()->next = next;
    }
    if (next) {
        next->prev.lock()->prev = prev;
    }
    reverse.lock()->remove();
}


#include <iostream>
#include <queue>

using namespace std;

void dijkstra(const Graph &g, int start) {
    using ll = long long;
    const ll INF = static_cast<ll>(1e18);
    int n = g.size();
    priority_queue<pair<ll, int>> q;
    vector<ll> dist(n, INF);
    dist[start] = 0;
    q.emplace(0, start);
    while (q.size() > 0) {
        ll d;
        int u;
        tie(d, u) = q.top();
        d = -d;
        q.pop();
        if (dist[u] < d) continue;
        for (spEdge e = g[u]->head; e; e = e->next) {
            if (dist[e->t] > dist[u] + e->c) {
                dist[e->t] = dist[u] + e->c;
                q.emplace(-dist[e->t], e->t);
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        long long int & d = dist[i];
        if (d == INF) {
            cout << "INF\n";
        } else {
            cout << d << '\n';
        }
    }
}

int main() {
    int n, m, r;
    cin >> n >> m >> r;
    Graph g(n);
    for (int i = 0; i < m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        g.add_uniedge(a, b, c);
    }
    // g.show();
    dijkstra(g, r);
}

Measured memory_bytes: 61556