Scout Outing

You are the scout master and you are planning a hike at Pulau Udang. There are $N (2 \leq N \leq 100)$ stations, and the travel time between two stations is a positive integer of at most $100$ that everybody knows.

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

Everybody starts at station 1 and takes some path to station $N$. At each forked junction the scouts split at the same time, one group per outgoing trail. At station 1, for example, the group splits in two: one explores the trail leading to station 5, and the other proceeds to station 6. The group that arrives at station 5 splits again, one part going to station 2 and the other heading for station 3. No trail is left unexplored. A route is fixed for every scout, so there are always enough people to split into the required number of groups, and your routing plan is known to everybody.

To ensure safety, a group that arrives at a station before the others waits until all of them have arrived safely, and only then do they split and set off at the same time. Assume the scouts start at time zero. The earliest group arrives at station 3 at time 9 (via station 5) and it has to wait for the two other groups coming from station 6 and station 4. When all 3 groups have arrived, they split into 2 groups and head for stations 2 and 7.

There is only one overall start station (station 1) and one overall end station (station $N$), every station is reachable from station 1, and station $N$ is reachable from every station. There is no cycle, otherwise you would go round and round.

Compute the earliest time $T$ when the last group can reach station $N$, assuming the scouts start at time zero. In the example above, $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 groups before setting off again, waiting time builds up. The waiting time at a station is the duration between the arrival times of the first and the last groups at that station. 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. In the same way, the waiting time at station 2 is 13.

Compute the total waiting time for the whole trip, which is the sum of the waiting times at all the stations. In the example, the total waiting time is 24.

At some stations the scouts do not need to set off right away once all the groups have arrived. They may rest and still reach station $N$ no later than time $T$. At station 5 the groups arrived at time 5, but they can rest until time 10 before setting off, without affecting $T$, the earliest arrival time of the last group at station 8. At station 2 they can rest for 1 further unit of time after all the groups have arrived. At all the other stations the scouts must set off without delay. So in this example there are two stations, 5 and 2, where the scouts may delay their departure.

Compute how many stations there are at which delayed departure is permitted.

The first line contains the number of stations $N (2 \leq N \leq 100)$ and the number of trails $M (1 \leq M \leq 1000)$. Each of the next $M$ lines contains 3 integers: the start station of a trail, its 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$.

Print 3 integers on a single line, separated by a space: the earliest time $T$ when the last group arrives at the final station $N$, the total waiting time, and the number of stations where delayed departure is permitted.