Taco's Network Reliability

You are given a network of workstations connected by communication cables. Each cable has a reliability score. The network is represented as an undirected graph with N workstations and M cables. Each cable connecting two workstations u and v has a reliability score r.

The reliability of a path from workstation S (the source) to workstation T (the target) is defined as the minimum reliability score among all cables on that path. Your task is to find the maximum possible reliability score (i.e., the maximum over all possible paths of the minimum edge reliability) from S to T. If there is no valid path from S to T, output -1.

In mathematical terms, if a path consists of edges with reliability scores \(r_1, r_2, \dots, r_k\), then the reliability of the path is \(\min(r_1, r_2, \dots, r_k)\). You are to determine:

[ \max_{\text{paths } P \text{ from } S \text{ to } T} \left(\min_{r \in P} r\right) ]

inputFormat

The first line of input contains four integers: N, M, S, and T, where N is the number of workstations, M is the number of cables, S is the starting workstation, and T is the target workstation.

Then M lines follow, each containing three integers u, v and r representing a cable connecting workstations u and v with reliability score r.

outputFormat

Output a single integer representing the maximum reliability score you can achieve on a path from workstation S to T. If no path exists from S to T, output -1.

5 6 1 5
1 2 95
2 3 70
3 4 90
4 5 80
1 3 60
2 5 50

70