Longest Common Segment of Shortest Paths

Elaxia and w** are both busy with their daily college routines, commuting between their dormitories and laboratories. They want to maximize the time they can spend together by choosing routes so that the overlapping (common) part of their commutes is as long as possible, while still following the shortest possible route for each of them.

Given an undirected weighted graph with \(n\) nodes and \(m\) edges, each edge has a travel time. You are also given two pairs of nodes: the first pair \((a, b)\) represents the start and destination for Elaxia, and the second pair \((c, d)\) represents the start and destination for w**. Both persons will take a shortest path (in term of total travel time) from their start to destination. Your task is to find the maximum total time (i.e., sum of edge weights) of a contiguous segment (i.e., consecutive edges) that is common to both shortest paths. Note that since the roads are undirected, a segment appearing in reverse order in one path is considered identical to that in the other.

Formally, if the shortest path from \(a\) to \(b\) is \(P = [p_0, p_1, \dots, p_k]\) and the shortest path from \(c\) to \(d\) is \(Q = [q_0, q_1, \dots, q_l]\), and if for some indices \(i\) and \(j\) a contiguous sequence of edges \((p_i, p_{i+1}), (p_{i+1}, p_{i+2}), \dots, (p_{i+t-1}, p_{i+t})\) appears in \(Q\) (either in the same order or reversed), then the sum \[ S = \sum_{r=i}^{i+t-1} w(p_r, p_{r+1}) \] is a candidate. Output the maximum such \(S\). If there is no common segment, output 0.

You may assume that a shortest path exists for both pairs.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of nodes and the number of edges: \(1 \leq n \leq 10^5, 1 \leq m \leq 10^5\).

The next \(m\) lines each contain three integers \(u\), \(v\), and \(w\) where \(u\) and \(v\) are endpoints of an edge and \(w\) is its travel time (a positive integer).

The last line contains four integers \(a\), \(b\), \(c\), and \(d\) representing the dormitory and laboratory numbers for Elaxia and w** respectively.

outputFormat

Output a single integer, the maximum total travel time of a contiguous common segment that appears in both of the shortest paths. If there is no common segment, output 0.

sample

6 7
1 2 3
2 3 4
3 4 5
2 5 2
5 4 2
4 6 1
3 6 6
1 6 2 6

5