[백준] 자바 문제 풀이 1939 : 골드3

import java.util.*;
import java.io.*;


public class Main {
    static int n, m;
    static int start, end;
    static int left = 0, right = 0;
    static int ans;
    static List<Graph>[] board = new ArrayList[10001];
    static boolean[] visited = new boolean[10001];

    static class Graph {
        int dest;
        int weight;

        Graph(int dest, int weight) {
            this.dest = dest;
            this.weight = weight;
        }
    }

    static boolean dfs(int s, int e, int w) {
        visited[s] = true;
        if (s == e) return true;

        List<Graph> gp = board[s];

        for(Graph g : gp) {
            if(visited[g.dest]) {
                continue;
            }

            if(w > g.weight) {
                continue;
            }

            boolean ret = dfs(g.dest, e, w);
            if(ret) return true;
        }
        return false;
    }

    static void solve() {

        while(left <= right) {
            int mid = (left + right) / 2;

            visited = new boolean[10001];

            boolean ret = dfs(start, end, mid);

            if(ret) {
                left = mid + 1;
                ans = mid;
            } else {
                right = mid - 1;
            }
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer str = new StringTokenizer(br.readLine());
        n = Integer.parseInt(str.nextToken());
        m = Integer.parseInt(str.nextToken());


        for (int i = 0; i < m; i++) {
            str = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(str.nextToken());
            int y = Integer.parseInt(str.nextToken());
            int w = Integer.parseInt(str.nextToken());

            if (board[x] == null) {
                board[x] = new ArrayList<>();
            }
            board[x].add(new Graph(y, w));

            if (board[y] == null) {
                board[y] = new ArrayList<>();
            }
            board[y].add(new Graph(x, w));
            right = Math.max(right, w);

        }

        str = new StringTokenizer(br.readLine());
        start = Integer.parseInt(str.nextToken());
        end = Integer.parseInt(str.nextToken());
        solve();

        bw.write(ans + "\n");
        bw.flush();

        br.close();
        bw.close();
    }

}