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.*;
import java.lang.*;

class Main {
	static class Graph {
		List<List<Edge>> adjList;

		public Graph(List<Edge> edges, int numVertices) {
			adjList = new ArrayList<>(numVertices);

			for(int i = 0; i < numVertices; i++) {
				adjList.add(new ArrayList<>());
			}

			for(Edge edge : edges) {
				adjList.get(edge.source).add(edge);
			}
		}
	}

	static class Edge {
		int source;
		int dest;
		int weight; // weight of edge

		public Edge(int s, int d, int w) {
			source = s;
			dest = d;
			weight = w;
		}
	}

	static class Node {
		int index;
		int weight; // weight in min-heap

		public Node(int i, int w) {
			index = i;
			weight = w;
		}
	}

	public static void findSSSP(Graph g, int source, int numVertices) {
		// Create min-heap and push the source into it
		PriorityQueue<Node> minHeap = new PriorityQueue<>((lhs, rhs) -> lhs.weight - rhs.weight);
		minHeap.add(new Node(source, 0)); // dist of source is 0

		// Initialize distance of all vertices to Infinity
		List<Integer> dist = new ArrayList<>(Collections.nCopies(numVertices, Integer.MAX_VALUE));

		// Set distance of source to 0
		dist.set(source, 0);

		// Mark processed vertices to True
		boolean[] done = new boolean[numVertices];
		done[source] = true; // no need to process source

		// Store predecessors of a vertex
		int[] prev = new int[numVertices];
		prev[source] = -1; // source has no predecessor

		while(!minHeap.isEmpty()) {
			// Get best vertex and remove from minHeap
			Node n = minHeap.poll();

			// Get vertex number
			int vertex = n.index;

			// Process all neighbors of vertex
			for(Edge edge : g.adjList.get(vertex)) {
				int dest = edge.dest;
				int weight = edge.weight;

				// Relaxation step
				if(!done[dest] && dist.get(dest) > dist.get(vertex) + weight) {
					// Update predecessor
					prev[dest] = vertex;
					dist.set(dest, dist.get(vertex) + weight);
					minHeap.add(new Node(dest, dist.get(dest)));
				}
			}

			// Finished processing vertex
			done[vertex] = true;
		}

		// Print results
		for(int i = 0; i < numVertices; i++) {
			int distance = dist.get(i);

			System.out.println(distance == Integer.MAX_VALUE ? "INF" : distance);
		}
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		int vertices = scanner.nextInt();
		int edges = scanner.nextInt();
		int source = scanner.nextInt();

		// Read edges
		List<Edge> edgesList = new ArrayList<>();
		for (int i = 0; i < edges; i++) {
			Edge edge = new Edge(scanner.nextInt(), scanner.nextInt(), scanner.nextInt());
			edgesList.add(edge);
		}

		// Create new graph
		Graph g = new Graph(edgesList, vertices);

		findSSSP(g, source, vertices);
	}
}