Задається зважений орієнтований граф та вершина ~s~ в ньому. Для кожної вершини ~u~ графа знайти довжину найкоротшої відстані від ~s~ до ~u~.

Input

Перший рядок вхідного файлу містить числа ~N~, ~M~, ~S~ (~2 \le N \le 2000~, ~1 \le M \le 5000~) – кількість вершин, ребер і номер виділеної вершини відповідно.

Наступні ~M~ рядків описують ребра. Кожне ребро задається стартовою вершиною, кінцевою вершиною та вагою самого ребра. Вага ребра - ціле число, яке не перевищує по модулю ~10^{15}~. Граф може містити кратні ребра та петлі.

Output

У вихідний файл вивести ~N~ рядків: для кожної вершини найкоротший шлях із ~s~ в ~u~, або «*» - якщо шляху не існує, або «-» якщо не існує найкоротшого шляху із ~s~ в ~u~.

Sample Input 1

6 7 1
1 2 10
2 3 5
1 3 100
3 5 7
5 4 10
4 3 -18
6 1 -1

Sample Output 1

0
10
-
-
-
*