+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت --- The subway system in Barareh consists of $n$ stations and $m$ subway lines. The stations are numbered from $1$ to $n$. Each line is managed by a company and each company has a unique identifier. The $i-th$ subway line $(1 \leq i \leq m)$ is managed by company $c_i$ and connects only two stations, $p_i$ and $q_i$, in both directions. When arriving at a station, if more than one subway line is connected to that station, passengers can easily switch between lines. The cost of using the subway in Barareh is a bit different. When a passenger uses only subway lines operated by a single company, he only need to pay $1$ Bararehian dollar. However, if a passenger changes their subway line at a station, and these two lines are managed by different companies, he have to pay an additional $1$ Bararehian dollar. In other words, the passenger pays $1$ Bararehian dollar at the first station, and then at each intermediate station, they only need to pay an additional $1$ Bararehian dollar if the two lines used for arriving and departing the station belong to different companies. Calculate the minimum cost required to travel from station $1$ to station $n$. # ورودی The first line of the input consists of two integers $n$ $(2 \leq n \leq 10^5)$ and $m$ $(0 \leq m \leq 2*10^5)$ separated by a space, which is the number of stations and the number of subway lines, respectively. Then, for each $1 \leq i \leq m$ , the $(i + 1)-th$ line of input contains three integers $p_i$, $q_i$, and $c_i$ $(1 \leq ci \leq 10^6)$, separated by a space $(p_i \neq q_i, 1 \leq p_i,q_i \leq n)$. # خروجی In the only line of output, if it is impossible to travel from station $1$ to station $n$ using the subway lines, print $1$. Otherwise, print the minimum cost required to travel from station $1$ to station $n$. ## ورودی نمونه 1 ``` 3 3 1 2 1 2 3 1 3 1 2 ``` ## خروجی نمونه 1 ``` 1 ``` ## ورودی نمونه 2 ``` 8 11 1 3 1 1 4 2 2 3 1 2 5 1 3 4 3 3 6 3 3 7 3 4 8 4 5 6 1 6 7 5 7 8 5 ``` ## خروجی نمونه 2 ``` 2 ``` In the example above, initially, one can traverse the following path by paying $1$ Bararehian dollar: $1->3->2->5->6$ Then, with another $1$ Bararehian dollar payment, continue the path as follows: $6-> 7 ->8$.

حل سؤال در بانک سؤالات