Fastest Transmission Time in a Computer Network

In the Internet network, not every computer is directly connected with each other. Some computers are connected by one-way links such that a connection from $$A$$ to $$B$$ does not necessarily imply a connection from $$B$$ to $$A$$. Moreover, different connections may take different amounts of time. Importantly, if there exists a connection from $$A$$ to $$B$$ and a connection from $$B$$ to $$A$$, then computers $$A$$ and $$B$$ are considered to be in the same local area network (LAN), and the transmission time between them is $$0$$.

You are given the network configuration. Your task is to determine the minimum transmission time from computer $$1$$ (source) to computer $$n$$ (destination).

inputFormat

The first line contains two integers $$n$$ and $$m$$, representing the number of computers and the number of directed connections, respectively.

Each of the following $$m$$ lines contains three integers $$u$$, $$v$$, and $$w$$, indicating that there is a directed connection from computer $$u$$ to computer $$v$$ with transmission time $$w$$.

outputFormat

Output a single integer: the minimum transmission time from computer $$1$$ to computer $$n$$.

sample

4 4
1 2 3
2 1 4
2 3 5
3 4 1

6