template<class T> class weighted {
  T val;
public:
  using weight_type = weighted<T>;
  weighted() : val(T()) { }
  weighted(const T& t) : val(t) {  }
  weighted(const weighted& w) : val(w.val) {  }
  weight_type& operator=(const T& t) {
    val = t;
    return *this;
  }
  weight_type& operator=(const weight_type& w) {
    val = w.val;
    return *this;
  }
  weight_type operator+(const weight_type& w) const{
    return weight_type(val + w.val);
  }
  bool operator<(const weight_type& w) const{
    return val < w.val;
  }
  bool operator>(const weight_type& w) const{
    return val > w.val;
  }
  bool operator==(const weight_type& w) const{
    return val == w.val;
  }
  bool operator!=(const weight_type& w) const{
    return val != w.val;
  }
  T get() const {
    return val;
  }
  static T zero() { return T(); }
};

#include <list>


template<class VP,class EP> class edge;

template<class VP,class EP>
class vertex {
public:
  using vertex_prop = VP;
  using edge_prop = EP;
  using vertex_type = vertex<VP,EP>;
  using edge_type = edge<VP,EP>;
  using vprop_iterator = typename std::list<vertex_prop>::iterator;
  using edge_iteraotr = typename std::list<edge_type>::iterator;
  using adjacency_type = std::list<edge_iteraotr>;
protected:
  adjacency_type de;
  vprop_iterator vp;
public:
  const int g_id;
  const int id;
  vertex(int g_id,int id , const vprop_iterator& vp) : g_id(g_id), id(id), vp(vp) {}

  const adjacency_type& delta() const { return de; } 
  adjacency_type& delta() { return de; }
  const vertex_prop& prop() const { return *vp; }
  vertex_prop& prop() { return *vp; }
};


#include <list>

template<class VP,class EP> class vertex;

template<class VP,class EP>
class edge {
public:
  using vertex_prop = VP;
  using edge_prop = EP;
  using vertex_type = vertex<VP,EP>;
  using edge_type = edge<VP,EP>;
  using vertex_iterator = typename std::list<vertex_type>::iterator;
  using eprop_iterator = typename std::list<edge_prop>::iterator;
protected:
  eprop_iterator ep;
  vertex_iterator ifrom;
  vertex_iterator ito;
public:
  const int g_id;
  const int id;
  edge(int g_id, int id, const vertex_iterator& ifrom, const vertex_iterator& ito,const eprop_iterator& ep)
    : g_id(g_id),id(id), ifrom(ifrom), ito(ito), ep(ep) {  }
  const vertex_iterator& from() const { return ifrom; } 
  vertex_iterator& from() { return ifrom; }
  const vertex_iterator& to() const { return ito; } 
  vertex_iterator& to() { return ito; }
  const edge_prop& prop() const { return *ep; }
  edge_prop& prop() { return *ep; }
};

#include <list>
#include <vector>

static int graph_id_ = 0;

template<class VP,class EP>
class graph {
public:
  using vertex_prop = VP;
  using edge_prop = EP;
  using vertex_type = vertex<VP,EP>;
  using edge_type = edge<VP,EP>;
  using vertex_iterator = typename std::list<vertex_type>::iterator;
protected:
  std::list<vertex_prop> vps;
  std::list<edge_prop> eps;
  std::list<vertex_type> vs;
  std::list<edge_type> es;

  std::vector<vertex_iterator> ivs;
  int V;
  int E;
public:
  const int g_id;
  graph() : g_id(graph_id_++), V(0), E(0) {}
  virtual vertex_iterator add_vertex(const vertex_prop& vp) = 0;
  virtual void add_edge(vertex_iterator& ifrom, vertex_iterator& ito, const edge_prop& ep) = 0;

  const std::vector<vertex_iterator> vertices() const { return ivs; }

  const vertex_iterator& operator[](int i) const { return ivs[i]; }
  vertex_iterator& operator[](int i) { return ivs[i]; }

  int vertices_cnt() const { return V; }
  int edge_cnt() const { return E; }
};

template<class VP,class EP>
class directed_graph : public graph<VP,EP> {
public:
  using vertex_prop = VP;
  using edge_prop = EP;
  using vertex_type = vertex<VP,EP>;
  using edge_type = edge<VP,EP>;
  using vertex_iterator = typename std::list<vertex_type>::iterator;
public:
  directed_graph() : graph<VP,EP>() {}
  directed_graph(int sz) : graph<VP,EP>() {
    for(int i = 0;i < sz;i++) { 
      this->add_vertex(vertex_prop());
    }
  }
  vertex_iterator add_vertex(const vertex_prop& vp) {
    this->vps.push_back(vp);
    this->vs.push_back(vertex_type(this->g_id,this->V, --this->vps.end()));
    this->ivs.push_back(--this->vs.end());
    this->V++;
    return --this->vs.end();
  }
  void add_edge(vertex_iterator& ifrom, vertex_iterator& ito, const edge_prop& ep) {
    if(ifrom->g_id != this->g_id || ifrom->g_id != ito->g_id) return;
    this->eps.push_back(ep);
    this->es.push_back(edge_type(this->g_id,this->E,ifrom,ito,--this->eps.end()));
    ifrom->delta().push_back(--this->es.end());
    this->E++;
  }
};

#include <queue>
#include <vector>
#include <set>
#include <functional>
template<class VP, class EP, class WW>
std::vector<weighted<WW>> dijkstra(const directed_graph<VP,EP>& g,typename directed_graph<VP,EP>::vertex_iterator s, std::function<weighted<WW>(const EP&)> f) {
    using W = weighted<WW>;
    using V = typename directed_graph<VP,EP>::vertex_iterator;
    using P = std::pair<W,int>;
    int n = g.vertices_cnt();
    std::priority_queue<P,std::vector<P>,std::greater<P>> que;
    std::vector<W> dist(n,-1);
    dist[s->id] = W::zero();
    que.push({dist[s->id], s->id});
    while(!que.empty()) {
        V v = g[que.top().second];
        W d = que.top().first;
        que.pop();
        if(dist[v->id] < d) continue;
        for(auto e : v->delta()) {
            if(dist[e->to()->id] == -1 || dist[e->to()->id] > d + f(e->prop())) {
                dist[e->to()->id] = d + f(e->prop());
                que.push({dist[e->to()->id], e->to()->id});
            }
        }
    }

    return dist;
}

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int main() {
  int V,E,r;
  cin >> V >> E >> r;
  directed_graph<int,i64> g(V);
  rep(i,0,E - 1) {
    int s,t;
    i64 d;
    cin >> s >> t >> d;
    g.add_edge(g[s],g[t],d);
  }
  auto dist = dijkstra<int,i64,i64>(g,g[r],[](const i64& d){return weighted<i64>(d);});
  for(auto d : dist) {
    if(d == -1) {
      cout << "INF" << endl;
    }
    else {
      cout << d.get() << endl;
    }
  }
}



Measured memory_bytes: 76776