import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
public class dijkstra_queue {
static int INF = 0x3f3f3f3f;
//将权值按升序排序
static Comparator<Node>com = new Comparator<>() {
public int compare(Node o1, Node o2) {
return o1.val-o2.val;
}
};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();//边数
int end = sc.nextInt();//终点
int[] dis = new int[n];//权值
int[][] map = new int[n][n];//图
//邻接矩阵存图
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
map[i][j] = INF;
}
}
for(int i = 0;i<m;i++){
int n1 = sc.nextInt();
int n2 = sc.nextInt();
int v = sc.nextInt();
//无向图
map[n2][n1] = v;
map[n1][n2] = v;
}
//起点为0
dijkstra(0,dis,map);
int ans = dis[end];
System.out.println(ans);
}
//核心代码
public static void dijkstra(int start,int[] dis,int[][] map){
boolean[] vis = new boolean[map.length];
Queue<Node> pq = new PriorityQueue<>(com);//构造小顶堆
pq.add(new Node(start,0));//将起点add到堆中
//初始化
for(int i = 0;i < map.length;i++){
vis[i] = false;
dis[i] = INF;
}
dis[start] = 0;
while(!pq.isEmpty()){
Node node = pq.poll();
int bian = node.side;
if(vis[bian] == true){
continue;
}
vis[bian] = true;
for(int i = 0;i<map.length;i++){
if(vis[i] == false && map[bian][i] + node.val < dis[i]){
dis[i] = map[bian][i] + node.val;
pq.add(new Node(i,dis[i]));
}
}
}
}
}
//节点类
class Node {
public int side;
public int val;
public Node(int side, int val) {
this.side = side;
this.val = val;
}
}
