他所在的城市可以看成一个N个点，M条边的网络。他告诉你他的家标号X1，他的学校标号Y1，MM的家标号X2以及MM每天所到的标号Y2。在这个城市中，每条边都有Xi，Yi，Di，分别表示这条边起点，终点，路径长度。注：所有边都是无向边，即只能从Xi走向Yi，也可以从Yi走向Xi。小X与MM，都会走最短的路程以节省时间， 他想尽可能长的与MM同路。但他只知道想MM了，算不出来他每天最多可以有多长路径与MM同路。所以，只好来找学OI的你来帮助他。

第一行六个整数，N，M，X1，Y1，X2，Y2，分别表示点的个数，边的个数，小X的起点和终点，MM的起点和终点。 以后2~M+1行，每行有三个整数Xi,Yi,Di。第i行表示第i-1条边的起点，终点，以及路径长度。

一行一个整数，为小X最大与MM同路的路程。

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

1

小X每天去上学都发现有某MM与其同路，慢慢的小X竟然暗恋上了这个同路的MM。经过多次尾随,小X终于找到了这个MM的家和每天要去的地方。