PROGRAMMING:Spring Tour

It's sunny in spring. On a whim, Xiao Song wants to ride a bike outside the school. But there's more than one way to get to his destination. He wants to get to his destination as soon as possible without having to ride too far,
Can you help him?
###Input format:
The input contains a test data, the first line has three integers n (2 < = n < = 1000), the number of possible locations on the way, and the location number 1 ~ n; M (1 < = m < = 10000) is the number of paths; D (2 < = d < = n), destination number; The school is the starting point, and the default value is 1. Next, line M:
x y time dist ，
X, y is the place where x and y can reach each other. Time and dist are the time and distance from X to y or y to x respectively.
###Output format:
Output "time spent + space + distance to ride + space + path from school to destination" in the following format. The two places in the path are separated by an arrow (- >)（ See output sample for details)
###Input example:
```in
7 8 7
1 2 1 1
1 3 1 1
2 4 1 2
3 4 1 1
4 5 1 2
4 6 1 1
5 7 1 1
6 7 2 1
```
###Output example:
```out
4 5 1->3->4->5->7
```






answer：If there is no answer, please comment