# 狄杰斯特拉

给定一张有向加权图，图中每条边的权重均为正整数。现在你需要从图中的一个起点出发，找到到达一个特定节点的最短路径。请编写一个程序，读入有向加权图和起点、终点，输出从起点到终点的最短距离。

## 输入描述

第一行包含三个整数n，m，s，分别表示节点数、边数和起点编号。节点编号从1到n。

接下来m行，每行包含三个整数u，v，w，表示u到v有一条有向边，边权为w。

1≤n≤1e5，1≤m≤2e5，1≤s≤n，1≤u,v≤n，1≤w≤1e9

## 输出描述

共一行，包含一个整数，表示从起点到终点的最短距离，如果不存在从起点到终点的路径，则输出INF。


## 输入样例

6 9 1
1 2 2
1 3 1
2 3 2
2 4 3
3 4 1
3 5 3
4 6 4
5 4 2
5 6 1

## 输出样例

8

## 提示

对于40%的数据，1≤n≤1e3，1≤m≤1e4，1≤w≤100。

对于100%的数据，有解保证存在且最大点数不超过1e5，边数不超过2e5。