小C终于被小X感动了，于是决定与他看电影，然而小X距离电影院非常远，现在假设每条道路需要花费小X的时间为1，由于有数以万计的好朋友沿路祝贺，导致小X在通过某些路不得不耗费1的时间来和他们聊天，尽管他希望尽早见到小C，所以他希望找到一条最快时间到达电影院的路。

   一开始小X在1号点，共有N个点，M条路，电影院为T号点。

   第一行2个正整数，分别为n，m，t  

 以下m行，每行3个数，表示连接的编号以及权值   （注意，可能会有重边）

 一行一个数，表示1到t的最短路

10 12 6
3 9 2
6 9 2
6 2 1
3 1 1
1 9 2
2 8 2
7 10 1
7 2 1
10 0 1
8 1 1
1 5 2
3 7 2

4