Sherlock loves to travel! This time, he is touring the city of London with Watson. Sherlock is in a playful mood today so he throws a challenge to Watson-
Given two cities $$A$$ and $$B$$, Sherlock will take the shortest path between the cities to travel. He also has a magic spell which destroys all the roads occurring in that path. Now, he asks Watson to tell him the shortest path from $$A$$ to $$B$$ in the new graph formed if there exists a path, or else print -1.
First line contains two space separated integers $$N$$ and $$M$$, the number of cities and number of roads respectively.
Second line contains integers $$A$$ and $$B$$.
Next $$M$$ lines contains three space separated integers $$u$$, $$v$$, $$w$$, denoting there is a road between cities $$u$$ and $$v$$ with length $$w$$.
Output the answer to the challenge posted by Sherlock.