using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Threading.Tasks;
namespace Project1
{
internal class Algorithm
{
static void Main(string[] args)
{
//StreamReader sr = new StreamReader(Console.OpenStandardInput());
//Console.WriteLine(sr);
//StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
(int, int) test = (0, 1);
(int, int) test2 = (0, -1);
Console.WriteLine(test.CompareTo(test2));
//노드의 개수, 간선의 개수, 시작 노드 번호 입력 받기
//int[] input = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
int v = input[0]; int e = input[1];
//int k = int.Parse(sr.ReadLine());
int k = int.Parse(Console.ReadLine());
List<List<(int, int)>> edgesList = new List<List<(int, int)>>();
//정점 생성
for (int i = 0; i <= v; i++)
edgesList.Add(new List<(int, int)>());
//각 정점마다 연결된 정점과 가중치 저장
for (int i = 0; i < e; i++)
{
//int[] edges = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
int[] edges = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
edgesList[edges[0]].Add((edges[1], edges[2]));
}
//값과 배열 초기화, 생성
bool[] visited = new bool[v + 1];
int INF = 2000000000;
int[] distance = new int[v + 1];
for (int i = 1; i < v + 1; i++)
distance[i] = INF;
int[] previous = new int[v + 1];
for (int i = 1; i < v + 1; i++)
previous[i] = -1;
Dijkstra(k); //k = 시작점
void Dijkstra(int s)
{
PriorityQueue<(int, int)> q = new PriorityQueue<(int, int)>();
q.Enqueue((0, s));
distance[s] = 0;
while (q.Count() > 0)
{
(int shortDistance, int currentNode) = q.Dequeue();
//if (distance[currentNode] < shortDistance) continue;
foreach (var adjNode in edgesList[currentNode])
{
int cost = distance[currentNode] + adjNode.Item2; //(int,int)의 2번째값
int nextNode = adjNode.Item1;
if (cost < distance[nextNode])
{
distance[nextNode] = cost;
//previous[nextNode] = currentNode;
q.Enqueue((cost, nextNode));
}
}
}
}
for (int i = 1; i < v + 1; i++)
if (distance[i] == INF)
//sw.WriteLine("INF");
Console.WriteLine("INF");
else
//sw.WriteLine(distance[i]);
Console.WriteLine(distance[i]);
//sr.Close();
//sw.Close();
}
}
//최소힙 우선순위 큐
public class PriorityQueue<T> where T : IComparable<T>
{
List<T> _heap = new List<T>();
public void Enqueue(T num)
{
_heap.Add(num);
int myIndex = _heap.Count() - 1;
while (true)
{
int parentIndex = (myIndex - 1) / 2; // 0일때 0, 1일때 0 ,2일때 0, 3일때 1
if (_heap[myIndex].CompareTo(_heap[parentIndex]) < 0) //(int,int) compareTo 하면 앞쪽거 먼저 비교, 앞쪽이 똑같다면 뒤쪽도 비교,
// 뒤쪽도 똑같다면 0 출력 (비교해서 똑같으면 0, 작으면 -1, 크면 1)
// 이 if가 의미하는건 힙에서 myIndex의 값이 더 작다는 뜻
{
var temp = _heap[myIndex];
_heap[myIndex] = _heap[parentIndex];
_heap[parentIndex] = temp;
myIndex = parentIndex;
}
else
break;
}
}
public T Dequeue()
{
int lastIndex = _heap.Count() - 1;
T last = _heap[lastIndex];
var temp = _heap[0];
_heap[0] = _heap[lastIndex];
_heap[lastIndex] = temp;
_heap.RemoveAt(lastIndex--);
int myIndex = 0;
while (true)
{
var tempIndex = myIndex;
int left = 2 * myIndex + 1;
int right = 2 * myIndex + 2;
if (left <= lastIndex && _heap[myIndex].CompareTo(_heap[left]) > 0)
myIndex = left;
if (right <= lastIndex && _heap[myIndex].CompareTo(_heap[right]) > 0)
myIndex = right;
if (tempIndex == myIndex) break;
var tempNum = _heap[tempIndex];
_heap[tempIndex] = _heap[myIndex];
_heap[myIndex] = tempNum;
}
return temp;
}
public int Count()
{
return _heap.Count();
}
}
}
/*
0
2
3
7
INF
*/
/*
첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다.
시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.
*/
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
{
}
0, 1 디큐
currentNode = 1
var adjNode in edgesList[1]
{
adjNode.item2 = 2;
그래서 cost 는 0 + 2가 들어감
nextNode = 2 // 1 2 2
if(cost < distance[2])
2 < 20억 이므로
{
2까지 가는 distance (distance[2]) 는 2
(previous[2] = 1) (필요한가)
(2, 2) 인큐
}
adjNode.item2 = 3
그래서 cost는 0 + 3이 들어감
nextNode = 3 // 1 3 3
if(cost < distance[3])
3 < 20억 이므로
{
3까지 가는 distance (distance[3]) 는 3
(previous[3] = 1) (필요한가)
(3, 3) 인큐
}
}
(2,2) 디큐
currentNode = 2
var adjNode in edgesList[2]
{
adjNode.item2 = 4;
그래서 cost 는 2 + 4가 들어감
nextNode = 3 // 2 3 4
if(cost < distance[3])
6 < 3 이므로 false
{
}
adjNode.item2 = 5
그래서 cost는 2 + 5이 들어감
nextNode = 4 // 2 4 5
if(cost < distance[4])
7 < 20억 이므로
{
4까지 가는 distance (distance[4]) 는 7
(previous[4] = 2) (필요한가)
(7, 4) 인큐
}
}
(3,3) 디큐
currentNode = 3
var adjNode in edgesList[3]
{
adjNode.item2 = 6;
그래서 cost 는 3 + 6가 들어감
nextNode = 4 // 3 4 6
if(cost < distance[4])
9 < 7 이므로 false
{
}
}
(7,4) 디큐
currentNode = 4
var adjNode in edgeList[4]
{
없음
}
1 -> 0
2 -> 2
3 -> 3
4 -> 7
5 -> 20억