public class Solution {
    /**
     * @param n: maximum index of position.
     * @param m: the number of undirected edges.
     * @param x:
     * @param y:
     * @param w:
     * @return: return the minimum risk value.
     */
    public class Edge {
        int to, w;
        Edge(int to, int w) {
            this.to = to;
            this.w = w;
        }
    }
    public int dfs(int now, int target, int val, int res, boolean[] vis, List[] g) {
        if (now == target) {
            return val;
        }
        if (val >= res) {
            return Integer.MAX_VALUE;
        }
        vis[now] = true;
        for (int i = 0; i < g[now].size(); i++) {
            Edge edge = (Edge)g[now].get(i);
            if (vis[edge.to]) {
                continue;
            }
            res = Math.min(res, dfs(edge.to, target, Math.max(val, edge.w), res, vis, g));
        }
        vis[now] = false;
        return res;
    }
    public int getMinRiskValue(int n, int m, int[] x, int[] y, int[] w) {
        // Write your code here
        boolean[] vis = new boolean[n + 1];
        for (int i = 0; i < n + 1; i++) {
            vis[i] = false;
        }
        ArrayList[] g = new ArrayList[n + 1];
        for (int i = 0; i < n + 1; i++) {
            g[i] = new ArrayList<Edge>();
        }
        for (int i = 0; i < m; i++) {
            g[x[i]].add(new Edge(y[i], w[i]));
            g[y[i]].add(new Edge(x[i], w[i]));
        }
        return dfs(0, n, 0, Integer.MAX_VALUE, vis, g);
    }
}