春节到了，小童要给亲戚送年货，一直小童在编号为1的位置，他一共给n-1家亲戚送年货，由于每家要给的东西较多，所以每送一家，小童都需要回家再拿一份年货。现在我们给每家亲戚编号为2—n, 这些亲戚直接有m条道路相连，每条道路的距离为s。请你帮小童计算一些，送完所有年货，他一共要走多少路。
第一行包含三个数，n和m（1<n<30）以及起始节点。
接下来有m行，每行包含3个整数，x,y,s分别表示从编号x到编号y的距离是s.
一个整数，表示小童走的路程。
样例输入
5 7 1 1 2 2 1 3 4 1 4 7 2 3 1 2 5 2 3 4 1 3 5 6
样例输出
26
1<n<30