9925번 - Scout Outing 다국어

문제

You are the scout-master and are planning a hike at Pulau Udang. There are $N (2 \leq N \leq 100)$ stations and the travel time (a positive integer value $\leq 100)$ between two stations is made known to everybody.

The stations are numbered from 1 to $N$. The diagram below shows an example with $N = 8$ stations.

Everybody must start at station 1 and go through some path to arrive at station $N$. At each forked junction, the scouts must split at the same time to proceed to each of the forked routes. For example, at station 1, the group is split into two --- one explores the route leading to station 5, and the other proceeds to station 6. The group that arrives at station 5 must split into two again, one to go to station 2 and the other to head for station 3. In other words, no trail is left unexplored. A route has been fixed for each scout so that there are always enough people to split up into the required number of groups, and your routing plan is made known to everybody.

To ensure safety, if a group arrives at a station earlier than other groups, the early group must wait for the rest, until all have arrived safely, before they split to proceed on at the same time. For example, assuming that you start at time zero, the earliest group arrives at station 3 at time 9 (via station 5), and they have to wait for the other two groups coming from station 6 and station 4. When all the 3 groups have arrived, they split into 2 groups and head for stations 2 and 7.

Note that there is only one overall start station (at station 1) and one overall end station (at station $N$), every station is reachable from station 1, and station $N$ is reachable from all the stations. There is no cycle (otherwise you will go round and round!)

You are to compute the earliest time $T$ when the last group can reach station $N,ドル assuming that the scouts start at time zero. In the above example, $T = 35$. That is, the earliest time for the last group to reach the final station 8 is 35.

Since a group that arrives at a station must wait for the other group(s) to arrive before setting off again, this constitutes the waiting time. Formally, the waiting time at a station is the duration between the arrival times of the first and the last groups at that station. For example, at station 3, the first group arrived at time 9 (via station 5), and the last group arrived at time 14 (via stations 6 and 4), so the waiting time at station 3 is 5. Similarly, the waiting time at station 2 is 13.

You are to compute the total waiting time, which is the sum of waiting times at all the stations, for the whole trip. In our example, the total waiting time is 24.

At some stations, there is no need for the scouts to set off right away after all the groups have arrived there. They may actually take a rest and still would not arrive at station $N$ later than time $T$. For example, at station 5, the groups arrived at time 5, but can rest until time 10 before setting off, without affecting $T,ドル the earliest arrival time of the last group at station 8. Similarly, when all groups have arrived at station 2, they can rest for a further 1 unit of time. However, at all the other stations, the scouts must set off immediately without delay. Hence, for our example, there are two stations (stations 5 and 2) where the scouts may delay their departure.

You are to compute how many stations there are at which delayed departure is permitted.

입력

The input includes the integer $N (2\leq N\leq 100,ドル the number of stations) and the integer $M (1\leq M\leq 1000,ドル the number of edges) on the first line, followed by $M$ lines each containing 3 integers: the start station, the end station, and the time to travel from the start station to the end station. All values are separated by one or more spaces. The whole trip starts from station 1 at time zero, and ends at station $N$.

출력

The output should contain 3 integers, separated by a space, in a single line: (1) the earliest time $T$ when the last group arrives at the final station $N,ドル (2) the total waiting time, and (3) the number of stations where delayed departure is permitted.

제한

힌트