23736번 - Vertex Merge Game 다국어

Yunee is going to challenge Woongbae with a game that Yunee invented. Yunee's game is called the Vertex Merge Game and it is played on an edge-weighted connected graph. The game consists of several rounds, and each round proceeds as follows.

1. At the start of each round, Yunee colors each vertex either red or blue. There should be at least one red vertex and one blue vertex after coloring.
2. Yunee receives points equal to $\text{(the number of red vertices)} \times \text{(the number of blue vertices)}$.
3. Woongbae selects an edge that connects a red vertex and a blue vertex.
4. Woongbae receives points equal to the weight of the selected edge.
5. Merge the two vertices at the ends of the selected edge. All edges are preserved after merging.

Repeat the rounds until there is only one vertex left in the graph. Then the game ends, and the person with higher total points wins the game.

Given a graph, find out who wins the game when both Yunee and Woongbae play the game optimally. Note that their goal is to win the game, not to maximize their points.

The first line contains two integers $N$ and $M$ $(2\leq N \leq 100,000, 1\leq M \leq 300,000)$. $N$ is the number of vertices and $M$ is the number of edges.

The next $M$ lines describe the edges of the graph. The $i$-th line contains three integers $u_i, v_i, w_i$ $(1\leq u_i, v_i \leq N, 0 \leq w_i \leq 10^9)$. It represents an edge connecting $u_i$ and $v_i$ with a weight $w_i$.

It is guaranteed that the given graph is connected.

If Yunee wins, output win. If Woongbae wins, output lose. If there is a tie, output tie.