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.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    private static Queue<Node> queue = new PriorityQueue<Node>(new Comparator<Node>() {
        @Override
        public int compare(Node o1, Node o2) {
            return o1.dist - o2.dist;
        }
    });

    private static List<Node> nodeList = new ArrayList<Node>();

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int v = Integer.parseInt(scan.next());
        int e = Integer.parseInt(scan.next());
        int r = Integer.parseInt(scan.next());

        List<List<Edge>> edgeList = new ArrayList<List<Edge>>();
        for (int i = 0; i < v; i++) {
            List<Edge> list = new ArrayList<Edge>();
            edgeList.add(list);
        }

        for (int i = 0; i < e; i++) {
            int s = Integer.parseInt(scan.next());
            int t = Integer.parseInt(scan.next());
            int d = Integer.parseInt(scan.next());
            edgeList.get(s).add(new Edge(s, t, d));
        }
        scan.close();

        for (int i = 0; i < v; i++) {
            nodeList.add(new Node(i, Integer.MAX_VALUE));
        }

        addNode(nodeList.get(r), 0);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            for (Edge edge : edgeList.get(node.id)) {
                addNode(nodeList.get(edge.t), node.dist + edge.d);
            }
        }

        for (Node node : nodeList) {
            if (node.dist != Integer.MAX_VALUE) {
                System.out.println(node.dist);
            } else {
                System.out.println("INF");
            }
        }

    }

    private static void addNode(Node node, int newDist) {
        if (node.dist <= newDist) {
            return;
        }

        node.dist = newDist;
        queue.add(node);
    }

    static class Edge {
        int s;
        int t;
        int d;

        public Edge(int s, int t, int d) {
            this.s = s;
            this.t = t;
            this.d = d;
        }
    }

    static class Node {
        int id;
        int dist;

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

}