SOLVE
LATER
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.
Input Format
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 Format
Output the answer to the challenge posted by Sherlock.