乱七八糟的图

Time Limit: 4000 ms Memory Limit: 65536 KiB

Problem Description

给一个连通无向图,图有n个顶点m条边,可能会有重边,无自环。然后给一个出发点st,现在这个st到其他每一个顶点都有一个最短距离。然后,让你删除一些边,剩下的边构成了一个新连通无向图,要求在新图中,出发点st到其他任何一个顶点的最短距离跟删边之前的最短距离保持不变,而且要求剩下的所有边的总长度最短。求出这个总长度。

Input

 多组输入。每组测试数据第一行为两个整数n(1<=n<=3*10^4)m(1<=m<=3*10^5).接下来m行,每行包括三个整数u,v,w.(1<=u,v<=n,1<=w<=10^9),表示顶点uv之间有一条长度为w的无向边。最后一行给出一个整数st(1<=st<=n)表示出发点。

Output

 每组测试数据输出一个整数表示最短的总长度。

Sample Input

3 3
1 2 1
2 3 1
1 3 2
3
4 4
1 2 1
2 3 1
3 4 1
4 1 2
4

Sample Output

2
4

Hint

 

Source

scf0920