정점 합치기 게임

Yunee는 자신이 만든 게임으로 Woongbae에게 도전하려고 한다. Yunee의 게임은 정점 합치기 게임이라고 하며, 간선에 가중치가 있는 연결 그래프에서 진행된다. 게임은 여러 라운드로 이루어지고, 각 라운드는 다음과 같이 진행된다.

1. 라운드가 시작될 때 Yunee는 각 정점을 빨간색 또는 파란색으로 칠한다. 칠한 뒤에는 빨간 정점이 하나 이상, 파란 정점이 하나 이상 있어야 한다.
2. Yunee는 $\text{(빨간 정점의 수)} \times \text{(파란 정점의 수)}$만큼 점수를 얻는다.
3. Woongbae는 빨간 정점과 파란 정점을 잇는 간선 하나를 선택한다.
4. Woongbae는 선택한 간선의 가중치만큼 점수를 얻는다.
5. 선택한 간선의 양 끝 정점 두 개를 합친다. 합친 뒤에도 모든 간선은 유지된다.

그래프에 정점이 하나만 남을 때까지 라운드를 반복한다. 그러면 게임이 끝나고, 총점이 더 높은 사람이 이긴다.

그래프가 주어졌을 때, Yunee와 Woongbae가 각자 최적으로 플레이하면 누가 이기는지 구하여라. 두 사람의 목표는 점수를 최대화하는 것이 아니라 게임에서 이기는 것이다.

첫째 줄에 정수 $N$과 $M$이 주어진다. $(2\leq N \leq 100,000, 1\leq M \leq 300,000)$ $N$은 정점의 수, $M$은 간선의 수이다.

다음 $M$개의 줄에 그래프의 간선이 주어진다. $i$번째 줄에는 세 정수 $u_i, v_i, w_i$가 주어진다. $(1\leq u_i, v_i \leq N, 0 \leq w_i \leq 10^9)$ 이는 $u_i$와 $v_i$를 잇는 가중치 $w_i$의 간선을 나타낸다.

주어진 그래프는 연결 그래프임이 보장된다.

Yunee가 이기면 win을 출력한다. Woongbae가 이기면 lose를 출력한다. 무승부면 tie를 출력한다.