알고스팟 자바(java) 해답 : TPATH

import java.util.*;

public class Main {
	static int n;
	static int e;
	static int l,h;
	static int [][] map;
	static int [][] length;
	static int [] size;
	static int [] cloud;
	static int [] visit;
	static int result;
	static int csize;
	
	public static void main(String args[]) throws Exception {
		
		map = new int[2000][2000];
		length = new int[2000][2000];
		size = new int[2000];
		cloud = new int[4000];
		visit = new int[2000];
		
		Scanner scanner = new Scanner(System.in);
		
		int testcase = scanner.nextInt();
		int a,b,c;
		
		for(int i = 0; i < testcase; i++){
			csize = 0;
			result = 0x7fffffff;
			Arrays.fill(size, 0);
			n = scanner.nextInt();
			e = scanner.nextInt();
			for(int j = 0; j < e; j++){
				a = scanner.nextInt();
				b = scanner.nextInt();
				c = scanner.nextInt();
				map[a][size[a]] = b;
				map[b][size[b]] = a;
				length[a][size[a]] = c;
				length[b][size[b]] = c;
				cloud[csize] = c;
				csize++;
				size[a]++;
				size[b]++;
			}
			Arrays.sort(cloud, 0, e);
			int temp;
			l = 0;
			h = 0;
			while(true){
				if(l > h || l == e)
					break;
				Arrays.fill(visit, 0);
				temp = decision(l, h);
				if(temp != h){
					h = temp;
					continue;
				}
				l++;
			}
			System.out.println(result);
		}
    }
	public static int decision(int lo, int hi){
		LinkedList<Integer> q = new LinkedList<Integer>();
		int j = cloud[lo];
		int k = cloud[hi];
		int now = 0;
		visit[now] = 1;
		q.add(now);
		
		while(!q.isEmpty()){
			
			now = q.removeFirst();
		
			for(int i = 0; i < size[now]; i++){
				if(length[now][i] <= k && length[now][i] >= j && visit[map[now][i]] == 0){
					visit[map[now][i]] = 1;
					q.add(map[now][i]);
				}
			}
		}
		if(visit[n-1] == 1){
			result = Math.min(result, k - j);
			return hi;
		}
		if(hi < e)
			return hi + 1;
		
		return hi;
	}
}