SP12056 FZ10B - Nubulsa Expo

你可能从未听说努布尔萨，这是一个位于太平洋的小岛国。它是一个尚未开发的国家，正面临海平面上升的威胁。科学家预计努布尔萨将在 2012 年消失。因此，努布尔萨政府希望在 2011 年举办世博会，以便让全世界的人们记住这个国家。 众所周知，世博园区由很多国家的博物馆组成。在园区内，各博物馆通过多条双向道路连接，所有博物馆都是直接或间接连通的。每条道路都有其游客容量，表示每秒最多可以通过这条路的人数。 由于经费有限，努布尔萨政府决定只设一个入口和一个出口。总统已经选择了一个博物馆作为入口，现在轮到世博负责人乌祖拉决定出口的博物馆。 乌祖拉曾在上海世博会上见识过人山人海的场面，他希望控制其世博园区的游客数量。为此，他打算选择一个博物馆作为出口，使得园区内的「最大游客流量」尽可能小。如果「最大游客流量」为 $W$，则意味着当世博园达到「稳定状态」时，每秒最多有 $W$ 人从入口进入。此「稳定状态」指的是园区内的游客数量保持恒定。 由于博物馆内只有一些海报，乌祖拉假设游客会持续移动，即使到达某个博物馆，也只是经过而已。

输入包含多组测试数据，直至输入一行 `0 0 0` 结束。 对于每组测试： - 第一行包含三个整数 $N, M, S$，分别表示博物馆的数量、道路的数量，以及作为入口的博物馆编号（博物馆编号从 1 到 $N$）。例如，`5 5 1` 表示有 5 个博物馆和 5 条道路连接它们，第 1 号博物馆是入口。 - 接下来的 $M$ 行，每行三个整数 $X, Y, K$，表示一条直接连接博物馆 $X$ 和 $Y$ 的道路，其游客容量为 $K$。

对于每组测试数据，输出一个整数，表示可以使「最大游客流量」最小的出口博物馆编号。如果有多个博物馆满足条件，可以输出其中任意一个。

- $1 < N \leq 100$ - $0 \leq M \leq 1000$ - $1 \leq S \leq N$ - $1 \leq X, Y \leq N$ - $1 \leq K \leq 10^5$ **本翻译由 AI 自动生成**