Yuki is a playful girl and she enjoys traveling.

One day, she is planning to play in the Disneyland. The resort is so large that she cannot find the shortest path between two sights immediately, so she wants to ask for your help.

Specifically, there are \(n\) sights and \(m\) roads in the Disneyland. Each road, with a certain distance, connects two sights. The sights are numbered from \(1\) to \(n\) and the roads are all bidirectional, that is the road from sight \(u\) to sight \(v\) can be passed from sight \(v\) to \(u\). You are asked to find the shortest distance between sight \(S\) and sight \(T\).

The first line contains two integers: \(n\) and \(m\) \((1 ≤ n ≤ 1\ 000,\ 1 \leq m \leq 5\ 000)\) — the number of sights and roads in Disneyland.

Each of the next \(m\) lines contains three space-separated integers: \(u\), \(v\) and \(w\) \((1 \leq u,\ v\leq n, \ 1 \leq w \leq 10^5)\), meaning that there is a bidirectional road from sight \(u\) to sight \(v\) with distance \(w\).

The last line contains two integers: \(S\) and \(T\) \((1 \leq S,\ T\leq n)\) — the origin and destination.

Print the result — the shortest distance between sight \(S\) and sight \(T\).

If there are no paths from sight \(S\) to sight \(T\), print \(-1\) instead.