Statement

Alice and Bob, a sibling pair, have been blessed with a weighted directed acyclic graph with N nodes and M edges under the Christmas tree. They are super competitive, so they decided to play a game on the graph. The game begins with a marker placed on vertex 1. At every turn, Alice and Bob make a move alternately with Alice beginning. In a move, the current player can move the marker from vertex u to vertex v if there is an edge from u to v. For such a move, the player needs to pay W_u->v money. The player who can not move the marker loses. They are incredibly smart, so they immediately understand who will win the game if they play optimally. Thus, the loser (being a sore loser) will do everything in their power to get the winner to pay as much money as possible. The loser does not care how much they have to pay. Given the graph, your task is to find who will win the game and the minimum amount the winner has to pay if both siblings play optimally.