'''
对边权值的上界进行二分搜索,验证上界是否有满足条件的路径方案存在
判断时候将所有边权值大于上界的边删掉,剩下的边每一条边拆成正反
两个方向的权值是1的有向边组成有向图,求有向图中1到N的最大流f
f数值就等价于从1到N的没有公共边的路径条数
需要注意的是原图是无向图,一条边拆出来的两条有向边是不能同时使用的,
但是特殊点在于,如果最大流两条边都使用了,那把这两条边上流过的流量删掉
剩下的流依然是一个最大流,所以任意一个最大流都必然能找到一个没有同时用
两条有向边的最大流与其对应,所以不考虑成对的有向边同时使用这个约束,
并不影响最后答案
'''
from typing import List
from collections import deque
class FortdFulkerson:
def __init__(self, edges, source_node, end_node, max_node_num, max_edge_num):
self.edges = edges[::]
self.source_node = source_node
self.end_node = end_node
self.max_edge_num = max_edge_num
self.max_node_num = max_node_num
def getMaxFlow(self):
e = [-1] * (self.max_edge_num*2 + 1)
f = [-1] * (self.max_edge_num*2 + 1)
ne = [-1] * (self.max_edge_num*2 + 1)
h = [-1] * (self.max_node_num + 1)
dis = [-1] * (self.max_node_num + 1)
cur = [-1] * (self.max_node_num + 1)
orig_flow = [0] * (self.max_edge_num + 1)
idx = 0
for a, b, w in self.edges:
e[idx], f[idx], ne[idx], h[a] = b, w, h[a], idx
idx += 1
e[idx], f[idx], ne[idx], h[b] = a, 0, h[b], idx
idx += 1
def bfs() -> bool:
for i in range(self.max_node_num + 1):
dis[i] = -1
que = deque()
que.append(self.source_node)
dis[self.source_node] = 0
cur[self.source_node] = h[self.source_node]
while len(que) > 0:
cur_node = que.popleft()
idx = h[cur_node]
while idx != -1:
next_node = e[idx]
if dis[next_node] == -1 and f[idx] > 0:
dis[next_node] = dis[cur_node] + 1
cur[next_node] = h[next_node]
if next_node == self.end_node:
return True
que.append(next_node)
idx = ne[idx]
return False
def dfs(node, limit) -> int:
if node == self.end_node:
return limit
flow = 0
idx = cur[node]
while idx != -1 and flow < limit:
cur[node] = idx
next_node = e[idx]
if dis[next_node] == dis[node]+1 and f[idx] > 0:
t = dfs(next_node, min(f[idx], limit - flow))
if t == 0:
dis[next_node] = -1
f[idx], f[idx^1], flow = f[idx]-t, f[idx^1]+t, flow+t
if self.edges[idx>>1][0] == node:
orig_flow[idx>>1] += t
else:
orig_flow[idx>>1] -= t
idx = ne[idx]
return flow
max_flow = 0
while bfs():
max_flow += dfs(self.source_node, 0x7fffffff)
return max_flow, [(self.edges[i][0], self.edges[i][1], orig_flow[i], self.edges[i][2]) for i in range(len(self.edges))]
n, m, t = map(int, input().split())
s = set()
edges = []
for _ in range(m):
a, b, w = map(int, input().split())
s.add(w)
edges.append((a, b, w))
edge_len = list(s)
edge_len.sort()
def valid(max_len) -> bool:
e = [(a, b, 1) for a, b, w in edges if w <= max_len]
e.extend([(b, a, 1) for a, b, w in edges if w <= max_len])
algo = FortdFulkerson(e, 1, n, max_node_num=n, max_edge_num=len(e))
return algo.getMaxFlow()[0] >= t
l, r = 0, len(edge_len)-1
ans = None
while l <= r:
mid = l + (r-l) // 2
if valid(edge_len[mid]):
ans = edge_len[mid]
r = mid - 1
else:
l = mid + 1
print(ans)