Problem: For a given weighted graph G(V, E) and a source r, find the source shortest path to each vertex from the source (SSSP: Single Source Shortest Path).

Constraints

* 1 ≤ |V| ≤ 100000
* 0 ≤ di ≤ 10000
* 0 ≤ |E| ≤ 500000
* There are no parallel edges
* There are no self-loops

Input

An edge-weighted graph G (V, E) and the source r.


|V| |E| r
s0 t0 d0
s1 t1 d1
:
s|E|-1 t|E|-1 d|E|-1


|V| is the number of vertices and |E| is the number of edges in G. The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively. r is the source of the graph.

si and ti represent source and target vertices of i-th edge (directed) and di represents the cost of the i-th edge.

Output

Print the costs of SSSP in the following format.


c0
c1
:
c|V|-1


The output consists of |V| lines. Print the cost of the shortest path from the source r to each vertex 0, 1, ... |V|-1 in order. If there is no path from the source to a vertex, print INF.

Examples

Input

4 5 0
0 1 1
0 2 4
1 2 2
2 3 1
1 3 5


Output

0
1
3
4


Input

4 6 1
0 1 1
0 2 4
2 0 1
1 2 2
3 1 1
3 2 5


Output

3
0
2
INF

Solution (in JAVA):

Solution:
import java.util.*;

public class Main {

    static class Edge {
        int from, to, cost;

        public Edge(int from, int to, int cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }
    }

    static class Node implements Comparable<Node> {
        int id, value;

        public Node(int id, int value) {
            this.id = id;
            this.value = value;
        }

        @Override
        public int compareTo(Node o) {
            return value - o.value;
        }
    }

    static int n;
    static List<List<Edge>> graph;
    static int[] dist;
    static int INF = 1000000100;

    static void dijkstra(int start) {
        dist = new int[n];
        Arrays.fill(dist, INF);
        dist[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>(n * 2);
        pq.offer(new Node(start, 0));

        boolean[] visited = new boolean[n];

        while (!pq.isEmpty()) {
            Node node = pq.poll();
            visited[node.id] = true;

            if (dist[node.id] < node.value) continue;;

            List<Edge> edges = graph.get(node.id);
            for (int i = 0; i < edges.size(); ++i) {
                Edge edge = edges.get(i);

                if (visited[edge.to]) continue;

                int newDist = dist[edge.from] + edge.cost;
                if (newDist < dist[edge.to]) {
                    dist[edge.to] = newDist;
                    pq.offer(new Node(edge.to, dist[edge.to]));
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int e = sc.nextInt();
        int r = sc.nextInt();
        graph = new ArrayList<>(n);
        for (int i = 0; i < n; ++i) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < e; ++i) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            int cost = sc.nextInt();
            graph.get(from).add(new Edge(from, to, cost));
        }

        dijkstra(r);

        for (int i = 0; i < n; ++i) {
            if (dist[i] == INF)
                System.out.println("INF");
            else
                System.out.println(dist[i]);
        }
    }
}