Задача G. Быстрый Дейкстра

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Вам необходимо написать программу, которая получает взвешенный ориентированный граф и находит в нем расстояния от вершины S до всех остальных вершин. Расстояние от вершины S до некоторой вершины W — это минимальная длина пути из S в W. Длина пути — это сумма весов всех рёбер, входящих в него.

Формат входного файла

Входной файл содержит три числа N, M и S. Вершины занумерованы целыми числами от 1 до N. S — это номер начальной вершины. M — это количество рёбер. Каждая из следующих M строк содержит три числа — номера начальной и конечной вершин текущего ребра и его вес соответственно. Все веса положительны. Между двумя вершинами может быть максимум одно ребро в каждом направлении.

Формат выходного файла

Выходной файл должен содержать N чисел. Каждое I-е число — это расстояние от вершины до S до вершины I. Если некоторые вершины недостижимы из S, то для для них должно быть выведено 1.

Ограничения

1 ≤ N, M ≤ 100000 Все веса меньше или равны 1000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5 3 1
1 2 5
1 3 7
3 4 10
0 5 7 17 -1

0.038s 0.009s 15