This page is still under construction.

Parts of this page are still being built. What you see may change.

Troop Movement

Interview

Time limit2sMemory limit256 MB

Summary
Find the route between two cities whose narrowest road is as wide as possible and report that width.
Level

Medium4 of 10

Topics
Minimum spanning tree, Union-find, Sorting
Solved
No attempts yet

Problem

During the war the king of the Northern Kingdom once drew up a plan to attack the Southern Kingdom. The territory of the two countries is described by p points and w roads. Every road is bidirectional, and each road has a width, so the number of soldiers that can pass along it is proportional to that width.

The king believed that soldiers are stronger when they move together, so he fixed one route to the Southern Kingdom in advance and sent every soldier along that route only. The king was shrewd, so he chose the route whose narrowest road is as wide as possible.

The record of which route he used burned during the war. The war history cannot be finished without it. You are a great scientist, so recover it.

Input

The first line contains the number of points p and the number of roads w, separated by a space. (2≤p≤10002 \le p \le 1000, 1≤w≤500001 \le w \le 50000)

The second line contains the capital of the Northern Kingdom c and the capital of the Southern Kingdom v, separated by a space. (0≤c,v<p0 \le c, v < p, c≠vc \ne v)

Each of the next w lines contains the two points wstart and wend that a road connects, followed by the width of that road wwidth, separated by spaces. (0≤wstart,wend<p0 \le wstart, wend < p, wstart≠wendwstart \ne wend, 1≤wwidth≤10001 \le wwidth \le 1000)

Several roads may connect the same pair of points. At least one route from c to v exists.

Output

Print on the first line the width of the narrowest road on the route the king chose.

Examples6

  1. Example 1

    Input
    7 11
3 5
0 1 15
0 2 23
1 2 16
1 3 27
2 4 3
2 6 21
3 4 14
3 5 10
4 5 50
4 6 9
5 6 42
    Expected output
    16

  2. Example 2

    Input
    2 1
0 1
0 1 1
    Expected output
    1

  3. Example 3

    Input
    2 3
1 0
0 1 7
0 1 1000
1 0 4
    Expected output
    1000

  4. Example 4

    Input
    5 4
0 4
0 1 100
1 2 5
2 3 100
3 4 100
    Expected output
    5

  5. Example 5

    Input
    6 7
0 5
0 1 9
1 5 9
0 2 8
2 3 8
3 4 8
4 5 8
1 3 2
    Expected output
    9

  6. Example 6

    Input
    6 6
0 5
0 5 3
0 1 6
1 2 6
2 3 6
3 4 6
4 5 6
    Expected output
    6