Who can escape the Nonary Game? The Nonary Game is a fictional game played in the video game trilogy of the same name. Your goal is to find how many players (at best) can escape a given game, in as few bytes of code as possible.

Rules of the game


There are 9 players, numbered 1 to 9.
All players start in the same room.
There are any number of doors, each one with a 1 to 9 number. There may be duplicate or missing door numbers.
Door are one-way connections between rooms. Each door can only be used once.
Only groups of 3 to 5 players can go through a door.
A group can only go through a door if the sum of their numbers modulo 9 matches the door’s number modulo 9.
Any player who goes through a 9 door escapes (wins).


Examples

┌───┬───┬───┐
│   6   4   9
│ &lt; │   |   |
│   3   5   9
└───┴───┴───┘ 


&lt; represents the starting point. All players start there.

In this setting, everybody can escape. There are various ways to achieve this, one of which is:


[1, 2, 3, 4, 5] go though door 6 ((1+2+3+4+5) % 9 = 6), while [6, 7, 8, 9] go through door 3 ((6+7+8+9) % 9 = 3). Everybody meets up in the second room.
[1, 2, 3, 7] go through door 4, while [4, 5, 6, 8, 9] go through door 5.
[1, 2, 3, 4, 8] go through one of the 9 doors, [5, 6, 7, 9] go through the other one.


┌───┬───┐
│   │   |
│ &lt; 8   9
│   │   |
└───┴───┘ 


This time, at most 4 people can escape:


[1, 3, 5, 8, 9] go through door 8.
[1, 3, 5, 9] go through door 9.


Other lists of survivors are possible, such as [2, 3, 4] or [1, 4, 6, 7], but there's no way for more than 4 people to escape.

The challenge

Given a map, output the maximum numbers of player who can escape.


Don’t worry, you don’t need to parse my awful diagrams! Input is a labeled directed graph, which you can represent in any convenient format (edge set, adjacency matrix...).
If your representation requires labels for rooms, you can use any consistent set of values. However, doors must be represented by the integers 1 to 9.
The input will always have at least one 9 door. All 9 doors always lead to the exit, while other doors never do.
Your submission can be a function or full program.
Standard loopholes are banned.


Test cases

Inputs are shown as lists of [door number, from room, to room] triplets, with 0 being the starting room and -1 being the exit. If you choose to use another format, you’ll have to convert them appropriately.

Input                                                                      Output
[[6, 0, 1], [3, 0, 1], [4, 1, 2], [5, 1, 2], [9, 2, -1], [9, 2, -1]]       9
[[8, 0, 1], [9, 1, -1]]                                                    4
[[9, 0, -1]]                                                               5
[[2, 0, 1], [1, 1, 2], [9, 2, -1]]                                         0
[[2, 0, 1], [3, 1, 2], [9, 2, -1]]                                         3
[[1, 0, 1], [9, 1, -1], [1, 0, 2], [9, 2, -1]]                             4
[[2, 0, 1], [3, 0, 1], [5, 1, 2], [4, 0, 2], [9, 2, -1], [9, 2, -1]]       8
[[3, 0, 1], [4, 0, 1], [5, 0, 1], [9, 1, -1], [7, 1, 2], [9, 2, -1]]       7
[[1, 0, 1], [2, 0, 1], [4, 0, 1], [9, 1, -1], [8, 1, 2], [9, 2, -1]]       6
[[6, 0, 1], [7, 0, 1], [9, 1, -1], [9, 1, -1]]                             7
JavaScript (ES6), 219 bytes
A slower but significantly shorter version using bitmasks instead of strings.

f=(D,P=[511],e=m=0)=&gt;P.map((X,r)=&gt;[...Array(-~X)].map((_,p)=&gt;D.map(([d,s,t],j)=&gt;(N=(g=(n,k)=&gt;n&amp;&amp;n%2+g(n&gt;&gt;1,++k,x+=n%2*k))(p&amp;=X,x=0))&lt;3|N&gt;5|r-s|x%9^d%9||f(D.filter(_=&gt;j--),A=[...P],e+!~t*N,A[r]^=p,A[t]^=p))),m=m&gt;e?m:e)|m

Try it online!
NB: The reason why it's slower is that we do not compute the powersets of the players. Given a bitmask of players \$X\$, we iterate on all \$(X \operatorname{AND} p)\$ for \$0\le p\le X\$ without deduplicating.

JavaScript (ES7),  293 272  271 bytes
Takes input in the format described in the challenge. This is a brute force search.

f=(D,P=[17**6+'8'],e=m=0)=&gt;P.map((X,r)=&gt;X&amp;&amp;[...X].reduce((a,x)=&gt;[...a,...a.map(y=&gt;y+x)],['']).map(p=&gt;D.map(([d,s,t],j)=&gt;p&lt;99|p[5]|r-s|eval([...p].join`+`)%9^d%9||f(D.filter(_=&gt;j--),A=[...P],e+!~t*p.length,A[r]=X.replace(eval(`/[${p}]/g`),''),A[t]=[A[t]]+p))),m=m&gt;e?m:e)|m

Try it online! (the first test case times out on TIO)
How?
The array P[] holds a list of strings describing the players in each room.
We start with P=['241375698'] (using \$17^6=24137569\$), which means that all players are initially located in room \$0\$.
For each room X at position r, we compute the powerset of X:
[...X].reduce((a, x) =&gt; [...a, ...a.map(y =&gt; y + x)], [''])

For each group of players p in there and for each door [d,s,t] at index j, we test if the group is unable to pass through the door:
                         // we can't pass if:
p &lt; 99 |                 // there are less than 3 players
p[5] |                   // or there are more than 5 players
r - s |                  // or the source room s is not equal to the current room
eval([...p].join`+`) % 9 // or the sum of the players modulo 9
^ d % 9                  // does not match the ID of the door modulo 9

If the group can pass, we do a recursive call:
f(                       //
  D.filter(_ =&gt; j--),    // remove the door that has just been used from D[]
  A = [...P],            // use a copy A[] of P[]
  e + !~t * p.length,    // if t = -1, add the length of p to e (number of escaped guys)
  A[r] = X.replace(      // remove the players from the source room A[r]
    eval(`/[${p}]/g`),   //
    ''                   //
  ),                     //
  A[t] = [A[t]] + p      // and append them to the target room A[t]
)                        //

We keep track of the maximum number of escaped players in m and eventually return it.