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

public class Main {
	private static final int INF = (int)1e9;

	static class Pair {
		int first;
		int second;

		public Pair(int first, int second) {
			this.first = first;
			this.second = second;
		}

		@Override
		public int hashCode() {
			return first + second;
		}

		@Override
		public boolean equals(Object other) {
			if (other instanceof Pair) {
				Pair p = (Pair)other;

				return p.first == first && p.second == second;
			}
			return false;
		}
	}

	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		try (Scanner in = new Scanner(System.in)) {
			int n = in.nextInt();
			List<Integer>[] g = new ArrayList[n];
			for (int i = 0; i < n; i++)
				g[i] = new ArrayList<>();

			int m = in.nextInt();
			int r = in.nextInt();
			Map<Pair, Integer> dist = new HashMap<>();
			for (int i = 0; i < m; i++) {
				int f = in.nextInt();
				int t = in.nextInt();
				int w = in.nextInt();

				g[f].add(t);
				dist.put(new Pair(f, t), w);
			}

			dijkstra(g, n, dist, r);
		} catch (Exception ex) {
			throw new RuntimeException(ex);
		}
	}

	public static void dijkstra(List<Integer> g[], int n, Map<Pair, Integer> dist, int s) {
		int[] d = new int[n];
		for (int i = 0; i < n; i++)
			d[i] = INF;

		d[s] = 0;
		PriorityQueue<Pair> pq = new PriorityQueue<>((x, y) -> x.second-y.second);
		pq.add(new Pair(s, 0));

		while (!pq.isEmpty()) {
			Pair p = pq.remove();

			for (int v : g[p.first]) {
				int dd = d[p.first] + dist.get(new Pair(p.first, v));
				if (dd < d[v]) {
					d[v] = dd;
					pq.add(new Pair(v, d[v]));
				}
			}
		}

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