Description

It is the war-torn year 2333. The world is divided into the XC alliance and the WJ alliance, and the two alliances are firing at each other. President ZR of country Q wants to make a very urgent state visit to the country of Yugo, but he cannot fly and can only travel by car. Because there are many different countries along the way and some are in anarchy, many roads are broken. There is no road that goes from a city to itself (who would do that...).

You need to determine a specific route. Since people from the WJ alliance may show up at any time, you must destroy all other roads incident to every city that the route passes through. You have a god’s-eye view and must help President ZR reach Yugo. You may change the state of some roads: you can close roads that are currently open or repair roads that are currently closed, but you cannot build new roads. You are given a map where ZR’s country is at city 1 and Yugo’s capital is at city $n$. Help President ZR reach Yugo as soon as possible. You will receive President ZR’s 3 billion deposit in the WJ Federal Bank and an army of 10 million people, and divide the Earth together with President ZR (the above is a scam...).

Description

Input Format

• The first line contains two integers $n$, $m$ ($2 \le n \le 1000$, $0 \le m \le 1000$). City $n$ is the capital of Yugo, and $m$ is the number of roads.
• The next $m$ lines each contain three integers $a$, $b$, $c$: $a$ is the start city, $b$ is the end city, and $c$ indicates the road’s state (1: passable / 0: impassable).

Output Format

The first line contains an integer $k$, the minimal number of road-state changes required.

4 4
1 2 1
1 3 0
2 3 1
3 4 1

3

Hint

Make road 1 2 1 impassable.

Make road 1 3 0 passable.

Make road 2 3 1 impassable.

And that will do.

Translated by ChatGPT 5