pub trait Property: Copy {}

impl<P> Property for P where P: Copy {}

pub trait ZeroP {
    fn zero() -> Self;
}

impl ZeroP for usize { fn zero() -> Self { 0 } }
impl ZeroP for u8 { fn zero() -> Self { 0 } }
impl ZeroP for u16 { fn zero() -> Self { 0 } }
impl ZeroP for u32 { fn zero() -> Self { 0 } }
impl ZeroP for u64 { fn zero() -> Self { 0 } }
impl ZeroP for isize { fn zero() -> Self { 0 } }
impl ZeroP for i8 { fn zero() -> Self { 0 } }
impl ZeroP for i16 { fn zero() -> Self { 0 } }
impl ZeroP for i32 { fn zero() -> Self { 0 } }
impl ZeroP for i64 { fn zero() -> Self { 0 } }

pub trait Weighted: Property + std::ops::Add<Output=Self> + std::cmp::Ord + ZeroP {}

impl<W> Weighted for W where W: Property + std::ops::Add<Output=W> + std::cmp::Ord + ZeroP {}

pub trait NonNegativeWeighted: Weighted {}

impl NonNegativeWeighted for usize {}

pub trait Capacity: Weighted + std::ops::Sub<Output=Self>{}

impl Capacity for usize {}

pub trait Cost: Capacity + std::ops::Mul<Output=Self> {}


#[derive(Clone,Copy,Eq,PartialEq,Debug)]
pub struct Vite(pub usize);

#[derive(Clone,Copy,Eq,PartialEq,Debug)]
pub struct Eite(pub usize);

pub trait Edge {
    fn from(&self) -> Vite;
    fn to(&self) -> Vite;
}

pub trait Vertex {
    fn new(id : usize) -> Self;
    fn id(&self) -> usize;
}

impl Vertex for usize {
    fn new(id: usize) -> Self { id }
    fn id(&self) -> usize { *self }
}

impl Edge for (usize,usize) { 
    fn from(&self) -> Vite { Vite(self.0) }
    fn to(&self) -> Vite { Vite(self.1) }
}

impl<P> Edge for (usize,usize,P) where P: Property { 
    fn from(&self) -> Vite { Vite(self.0) }
    fn to(&self) -> Vite { Vite(self.1) }
}

pub trait Graph<'a, V: Vertex, E: Edge> {
    type EsIter: std::iter::Iterator<Item=&'a Eite>;
    fn add_edge(&mut self, e: E);
    fn delta(&'a self, v: &Vite) -> Self::EsIter;
    fn edge(&self, e: &Eite) -> &E;
    fn vertex(&self, v: &Vite) -> &V;
    fn v_size(&self) -> usize;
    fn e_size(&self) -> usize;
}

pub fn from<E: Edge>(f: Vite, e: &E) -> Vite {
    if e.from() == f { e.from() }
    else { e.to() }
}

pub fn to<E: Edge>(f: Vite, e: &E) -> Vite {
    if e.from() == f { e.to() }
    else { e.from() }
}

pub trait Directed<'a,V: Vertex, E: Edge>: Graph<'a,V,E> {  }
pub trait Undirected<'a,V: Vertex, E: Edge>: Graph<'a,V,E> {  }
pub trait Bipartite<'a,V: Vertex, E: Edge>: Graph<'a,V,E> { 
    fn left_size(&self) -> usize;
    fn right_size(&self) -> usize;
    fn left_vs(&self) -> std::slice::Iter<Vite>;
    fn right_vs(&self) -> std::slice::Iter<Vite>;
}

pub struct DirectedGraph<V: Vertex, E: Edge> {
    n: usize,
    m: usize,
    g: Vec<Vec<Eite>>,
    es: Vec<E>,
    vs: Vec<V>
}

impl<'a,V: Vertex, E: Edge> Graph<'a,V,E> for DirectedGraph<V,E> {
    type EsIter = std::slice::Iter<'a,Eite>;
    fn add_edge(&mut self, e: E) {
        let ei = Eite(self.m);
        self.m += 1;
        self.g[e.from().0].push(ei);
        self.es.push(e);
    }
    fn delta(&'a self, v: &Vite) -> Self::EsIter {
        self.g[v.0].iter()
    }
    fn edge(&self, e: &Eite) -> &E {
        &self.es[e.0]
    }
    fn vertex(&self, v: &Vite) -> &V {
       &self.vs[v.0]
    }
    fn v_size(&self) -> usize {
        self.n
    }
    fn e_size(&self) -> usize {
        self.m
    }
}

impl<'a,V: Vertex, E: Edge> Directed<'a,V,E> for DirectedGraph<V,E> {  }

impl<V: Vertex, E: Edge> DirectedGraph<V,E> {
    pub fn new(n: usize) -> Self {
        let mut g = DirectedGraph {
            n: n,
            m: 0,
            g: vec![Vec::<Eite>::new(); n],
            es: Vec::<E>::new(),
            vs: Vec::<V>::new()
        };
        for i in 0..n {
            g.vs.push(V::new(i));
        }
        g
    }
}

use std::collections::vec_deque::*;
use std::cmp::max;

pub fn scaling_dijkstra_s3p<'a,V,E,G,F>(g: &'a G, s: Vite,fp: F) -> Vec<Option<usize>>
where V: Vertex ,E: Edge,G: Graph<'a,V,E>, F: Fn(&E) -> usize {
    let n = g.v_size();
    let mut mv = usize::zero();
    for i in 0..n {
        for e in g.delta(&Vite(i)) {
            mv = max(mv, fp(g.edge(e)));
        }
    }
    let mut cnt = 0usize;
    while mv > usize::zero() {
        mv = mv >> 1;
        cnt += 1;
    }

    let mut dist = vec![Some(usize::zero()); n];

    for k in (0..cnt+1).rev() {
        for i in 0..n {
            dist[i] = match dist[i] {
                Some(d) => Some(d * 2),
                None => None
            }
        }
        let mut temp = vec![None; n];
        temp[s.0] = Some(usize::zero());

        let mut vec : Vec<VecDeque<Vite>> = vec![VecDeque::<Vite>::new();n + 10];
        vec[0].push_back(s);

        for d in 0..vec.len() {
            while let Some(v) = vec[d].pop_front() {
                if temp[v.0].unwrap() < d { continue; }
                for ei in g.delta(&v) {
                    let e = g.edge(ei);
                    let to = to(v, e);
                    if dist[to.0] == None { continue; }
                    let c = (fp(e) >> k) + dist[v.0].unwrap() - dist[to.0].unwrap();
                    if d + c >= vec.len() { continue; }
                    if temp[to.0] == None {
                        temp[to.0] = Some(d + c);
                        vec[d + c].push_back(to);
                    }
                    else if temp[to.0].unwrap() > d + c {
                        temp[to.0] = Some(d + c);
                        vec[d + c].push_back(to);
                    }
                }
            }
        }

        for i in 0..n {
            dist[i] = if let (Some(d) , Some(t)) = (dist[i] , temp[i]) {
                Some(d + t)
            }
            else {
                None
            }
        }
    }
    dist
}

fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let v:Vec<usize> = s.trim().split_whitespace()
        .map(|e|e.parse().unwrap()).collect();
    let (n,m,r) = (v[0] , v[1] , v[2]);
    let mut g = DirectedGraph::<usize, (usize,usize,usize)>::new(n);
    for _ in 0..m{
        let mut t = String::new();
        std::io::stdin().read_line(&mut t).unwrap();
        let x:Vec<usize> = t.trim().split_whitespace()
            .map(|e|e.parse().unwrap()).collect();
        let (v,u,d) = (x[0],x[1],x[2]);
        g.add_edge((v,u,d));
    }
    let res = scaling_dijkstra_s3p(&g, Vite(r), |w| w.2);
    for d in res {
        match d {
            Some(i) => println!("{}" , i),
            None => println!("INF")
        }
    }
}



Measured memory_bytes: 36568