Under construction

Still being built. Things may change

Trip Compulsion

Interview

Time limit24sMemory limit1024 MB

Summary
Given a weighted undirected graph, find the minimum possible gap between the longest and shortest road on a path from start to end.
Level

Medium5 of 10

Topics
Sliding window, Union-find, Sorting, Graph
Solved
No attempts yet

Problem

Being a very quirky person, you have modeled your large neighbourhood as a set of numbered junctions and two-way roads connecting these junctions. Somewhat disturbingly, you have measured the length of each road in nanometers.

Whenever you take a trip from one junction to another, you note the lengths of the longest and shortest roads in your trip and compute the difference between them. Before you set out on a trip, you are overwhelmed by a strong urge to find the lowest possible difference among all trips with the same starting and ending junction as yours. Computing this on paper would take ages, and your trip is a little urgent (you must leave in the next 5 hours), so you decide to write a program.

Input

The first line contains T, the number of test cases. The first line of each test case contains two space separated numbers, N (the number of junctions) and R (the number of roads). The second line of each test case contains two space separated numbers, start (the starting junction of your trip) and end (the ending junction of your trip). Each of the next R lines contains three space separated numbers, from (the starting junction of a road), to (the ending junction of a road), and length (the length of the two-way road connecting from and to).

Output

For each test case, output a single line containing one integer, the lowest possible difference. If no trip is possible between start and end, output a single line saying "NO PATH" (quotes for clarity).

Constraints

  • 1≤T≤101 \le T \le 10
  • 2≤N≤20002 \le N \le 2000
  • 0≤R≤30000 \le R \le 3000
  • 0≤start,end,from,to<N0 \le start, end, from, to < N
  • 1≤length≤1 \le length \le 2,000,000,000
  • start and end will be different.

Examples1

  1. Example 1

    Input
    3
3 2
0 2
0 1 1000
1 2 5000
2 1
0 1
0 1 1000
2 0
0 1
    Expected output
    4000
0
NO PATH