重新排版的翻译

QU铁路是一家拥有N个站和M条线的铁路公司。我们为每站都分到了0~n-1的唯一站号（例如：珠江大道站，可以理解为一个站名，只是以数字作为代表）。 
每条线连接两个不同的站，可用于任一方向的移动。 此外，QU铁路使用票价表，因此票价根据距离逐渐变化。 从站A到另一个站B的票的价格是根据站A到站B的最短距离以票价表（即以一个固定的计算方式，票价表见图片1下方）确定的。
例子请参考以下图片：【图片1】![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT861/e1edf2b53d07b54aa0011336ee23e1466ad632dc.png)
票价：1km至6km为180日元（此处 円 即日元单位）
7km至15km为230日元，
16km至25km为400日元，
26km至40km为530日元，
41km至60km为740日元，
61km以上为820日元。 
在本例中，让我们考虑从0到6的票价。 
由于从起始车站到车站6的距离总计为41km，因此从起始车站到车站6的车票从票价表变为740日元。 
在QU铁路中，您还可以使用具有不同部分的多个票证从一个站点移动到另一个站点。 我将这称为分票。 
例如，如果您有接下来的2张票，则可以从0站移动到6站。
从起始站到车站1有：6km，180日元的车票。 
从1号站到6号站的车票：35公里，530日元
此时的总票价为180 + 530 = 710日元，比从0号站到6号站购买一张票便宜。
因此，在QU铁路中，由于票务分割，票价变得便宜。
此外，考虑如下使用三张票从站0移动到站6的情况。
从0号站到2号站的票：13米，230日元 
从2号站到4号站的票：14公里，230日元     	  从4号站到6号站的票：14公里，230日元
此时的总票价为230 + 230 + 230 = 690日元，并且会更便宜。 
节俭的女人希望通过成功使用这样的票证节省旅行费用。 
沃恩先生想从S站到G站，但如果可能的话，我们希望通过便宜的票价拆分来降低票价。
然而，沃恩先生买几张票是很麻烦的。 
沃恩先生认为他将使用最多两张票从S站转移到G站。 
因此，在上面的例子中，当Walmo先生从站0移动到站6时，需要710日元。 
你的工作是找到Walmo先生从S站转移到G站所需的最低运输费用。 
限制： 
2<=N<=30000 
1<=M<=60000 
1<=K<=300 
0<=S<N
0<=G<N 
SG 
对于任何  0≤i<M  ，                       		0≤a_i<N，
   0≤b_i<N，
   a _ i≠b_i  
对于任何  0≤i<j<M   ，
   {ai,bi}！={aj,bj}
对于任何  0≤i<M   ，
    1<=di<10的4次方  
	1=x_0＜x_1＜...＜x_{K-1}≦10^9  		1≦f_0＜f_1＜...＜f_{K-1}≦10^9 
存在至少一条最短路径。