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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class Main {
	// O(|E|log|V|) implementation of Dijkstra algorithm.
	static long[] dist;
	static long INF = 100000000000000000L;
	static ArrayList<ArrayList<Edge>> adj;
	
	static class Edge {
		int to;
		long w;
		Edge(int _to, long _w) {
			this.to = _to;
			this.w = _w;
		}
		
		@Override
		public String toString() {
			return "(to=" + to + ", w=" + w + ")";
		}
		
	}
	
	static class NextNode {
		int id;
		long cost;
		NextNode(int _id, long _cost) {
			id = _id; cost = _cost;
		}
	}
	
	static void initG(int V) { // V: the number of vertexes
		for(int i=0; i<V; i++) {
			adj.add(new ArrayList<Edge>());
		}
	}

	static void dijkstra(int s) {
		Arrays.fill(dist, INF);
		dist[s] = 0;
		PriorityQueue<NextNode> pq = new PriorityQueue<NextNode>(new Comparator<NextNode>() {
			public int compare(NextNode n1, NextNode n2) {
				if(n1.cost > n2.cost) return 1;
				else if(n1.cost==n2.cost) return 0;
				else return -1;
			}
		});
		pq.add(new NextNode(s, 0));
		while(!pq.isEmpty()) {
			NextNode cn = pq.poll();
			if(cn.cost > dist[cn.id]) continue;
			for(Edge e : adj.get(cn.id)) {
				if(cn.cost + e.w < dist[e.to]) {
					dist[e.to] = cn.cost + e.w;
					pq.add(new NextNode(e.to, dist[e.to]));
				}
			}
		}
	}
	
	// verified at http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2715447#1
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		PrintWriter pw=new PrintWriter(System.out);
		int V = sc.nextInt();
		int E = sc.nextInt();
		int r = sc.nextInt();
		dist = new long[V];
		adj = new ArrayList<ArrayList<Edge>>(V);
		initG(V);
		for(int i=0; i<E; i++) {
			int s = sc.nextInt();
			int t = sc.nextInt();
			int d = sc.nextInt();
			adj.get(s).add(new Edge(t, d));
		}
		dijkstra(r);
		for(int i=0; i<V; i++) {
			if(dist[i] == INF) {
				pw.println("INF");
			} else {
				pw.println(dist[i]);
			}
		}
		pw.close();
	}
	
	static class Scanner
	{
		BufferedReader br;
		StringTokenizer st;
		public Scanner(InputStream s)
		{
			br=new BufferedReader(new InputStreamReader(s));
		}
		public String nextLine() throws IOException
		{
			return br.readLine();
		}
		public String next() throws IOException
		{
			while(st==null || !st.hasMoreTokens())
				st=new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int nextInt() throws IOException
		{
			return Integer.parseInt(next());
			
		}
		public double nextDouble() throws IOException
		{
			return Double.parseDouble(next());
		}
		public boolean ready() throws IOException
		{
			return br.ready();
		}
		public long nextLong() throws IOException
		{
			return Long.parseLong(next());
		}
	}
	
}