using System;
using System.Collections.Generic;
using System.Linq;

class PriorityQueue<T> where T : IComparable<T> {
    private List<T> _buf = new List<T>();
    private IComparer<T> _comp;

    private void Swap(int a, int b) {
        T t = _buf[a];
        _buf[a] = _buf[b];
        _buf[b] = t;
    }

    private int Compare(T a, T b) {
        if (_comp == null) return a.CompareTo(b);
        return _comp.Compare(a, b);
    }

    public int Count { get { return _buf.Count; } }

    public PriorityQueue() {
    }

    public PriorityQueue(IComparer<T> comp) {
        _comp = comp;
    }

    public void Enqueue(T x) {
        _buf.Add(x);

        // shiftup
        int p = Count-1;
        while (p > 0) {
            int parent = (p - 1) / 2;
            if (Compare(_buf[parent], _buf[p]) <= 0)
                break;
            Swap(parent, p);
            p = parent;
        }
    }

    public T Dequeue() {
        if (Count == 0)
            throw new IndexOutOfRangeException();

        T ret = _buf[0];
        _buf[0] = _buf[Count-1];
        _buf.RemoveAt(Count-1);

        // shiftdown
        int p = 0;
        while (p < Count) {
            int c = p * 2 + 1; // ?????????
            if (c >= Count) break;

            if (c+1 < Count) { // c+1 ????????????
                if (Compare(_buf[c+1], _buf[c]) < 0) { // ??????????????????????°???????
                    c++;
                }
            }

            if (Compare(_buf[p], _buf[c]) <= 0)
                break;
            Swap(p, c);
            p = c;
        }

        return ret;
    }
}

struct D : IComparable<D> {
    public int node, cost;

    public int CompareTo(D o) {
        return cost - o.cost;
    }
}

struct Adj {
    public int next, cost;
}

class Program {
    static string ReadLine() { return Console.ReadLine(); }
    static int ReadInt() { return int.Parse(ReadLine()); }
    static int[] ReadInts() { return ReadLine().Split().Select(int.Parse).ToArray(); }
    static string[] ReadStrings() { return ReadLine().Split(); }

    static void Calc(int n, int r, Dictionary<int, List<Adj>> adj) {

        var dist = new int[n];
        for (int i = 0; i < dist.Length; i++) dist[i] = -1;
        var used = new int[n];
        var q = new PriorityQueue<D>();
        q.Enqueue(new D { node = r, cost = 0 });
        while (q.Count > 0) {
            D d = q.Dequeue();

            if (used[d.node]++ > 0) continue;
            dist[d.node] = d.cost;

            if (adj.ContainsKey(d.node)) {
                foreach (var t in adj[d.node]) {
                    q.Enqueue(new D { node = t.next, cost = d.cost + t.cost });
                }
            }
        }

        foreach (int d in dist) {
            if (d == -1) { // no path
                Console.WriteLine("INF");
            }
            else {
                Console.WriteLine(d);
            }
        }
    }

    static void Main() {
        var nmr = ReadInts();
        int n = nmr[0], m = nmr[1], r = nmr[2];

        var adj = new Dictionary<int, List<Adj>>();
        for (int i = 0; i < m; i++) {
            var abc = ReadInts();
            int a = abc[0];
            int b = abc[1];
            int c = abc[2];
            if (!adj.ContainsKey(a)) adj[a] = new List<Adj>();

            adj[a].Add(new Adj { next = b, cost = c });
        }

        Calc(n, r, adj);
    }
}

Measured memory_bytes: 37976