In the mystical realm of Algorithmland, a wise wizard has discovered a series of magical portals connecting different cities. There are $N$ cities numbered from $1$ to $N$, and exactly $M$ portals. Each portal allows travel in one direction only, taking a certain amount of time. The wizard's quest is to travel quickly from city $1$ to city $N$. Your task is to determine the minimum amount of time required to achieve this journey. If no valid route exists from city $1$ to city $N$, output $-1$. ## Input Format - The first line contains two space-separated integers, $N$ and $M$, where $N$ is the number of cities and $M$ is the number of magical portals. - Each of the next $M$ lines contains three space-separated integers: $u$, $v$, and $w$. The integer $u$ denotes the starting city, $v$ denotes the destination city of the portal, and $w$ is the time (in minutes) it takes to travel through that portal. ## Output Format - Output a single integer: the minimum time required to travel from city $1$ to city $N$. If there is no possible route, output $-1$. ## Examples #### Input 4 4 1 2 5 2 3 10 1 4 100 3 4 5 #### Output 20 #### Input 3 1 2 3 4 #### Output -1