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.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Comparator;

public class Main {
    static void dijkstra(ArrayList<Node> nodes, int start){
        Comparator<Node> comparator = new NodeCostComparator();
        PriorityQueue<Node> pq      = new PriorityQueue<Node>(100000, comparator);
        nodes.get(start).cost = 0;
        pq.add(nodes.get(start));
        
        while (!pq.isEmpty()){
        	Node done_node = pq.poll();
        	for (int i = 0; i < done_node.edge_to.size(); i++){
        		int to 	 	 = done_node.edge_to.get(i);
        		int cost 	 = done_node.edge_cost.get(i);
        		int new_cost = done_node.cost + cost;
        		int to_cost  = nodes.get(to).cost;
        		if (to_cost < 0 || new_cost < to_cost){
        			nodes.get(to).cost = new_cost;
        			if (!pq.contains(nodes.get(to))){
        				pq.add(nodes.get(to));
        			}
        		}
        	}
        }
    }
    static void print_results(ArrayList<Node> nodes){    
        for (int i = 0; i < nodes.size(); i++){
            int cst = nodes.get(i).cost;
            if (cst == -1){
                System.out.println("INF");
            }else{
                System.out.println(cst);
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int V = Integer.parseInt(line[0]);
        int E = Integer.parseInt(line[1]);
        int r = Integer.parseInt(line[2]);
        ArrayList<Node> nodes = new ArrayList<Node>();
        for (int i = 0; i < V; i++){
            ArrayList<Integer> edge_to   = new ArrayList<Integer>();
            ArrayList<Integer> edge_cost = new ArrayList<Integer>();
            Node node = new Node(-1, edge_to, edge_cost);
            nodes.add(node);
        }
        
        for (int i = 0; i < E; i++){
            String[] line2 = br.readLine().split(" ");
            int s = Integer.parseInt(line2[0]);
            int t = Integer.parseInt(line2[1]);
            int d = Integer.parseInt(line2[2]);
            nodes.get(s).edge_to.add(t);
            nodes.get(s).edge_cost.add(d);
        }
        dijkstra(nodes, r);
        print_results(nodes);
    }
}
class NodeCostComparator implements Comparator<Node>{
    @Override
    public int compare(Node x, Node y){
        int value = x.cost - y.cost;
        if (value < 0){
            return -1;
        }
        if (value > 0){
            return 1;
        }
        return 0;
    }
}

class Node{
    int cost = -1;
    ArrayList<Integer> edge_to   = new ArrayList<Integer>();
    ArrayList<Integer> edge_cost = new ArrayList<Integer>();
    
    Node(int cost, ArrayList<Integer> edge_to, ArrayList<Integer> edge_cost){
        this.cost       = cost;
        this.edge_to    = edge_to;
        this.edge_cost  = edge_cost;
    }
}