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.