Problem Description

Find the route with minimum traffic congestion between two cities. Given a graph of cities connected by roads with traffic weights, use a modified shortest path algorithm to find the path with minimum total congestion.

Input Format

First line: n (cities), m (roads), start city, end city. Next m lines: city1, city2, traffic_weight.

Output Format

Minimum total traffic congestion from start to end city, or -1 if no path exists.

Constraints

• 1 ≤ n ≤ 1000

• 1 ≤ m ≤ 5000

• 1 ≤ traffic weight ≤ 1000

• Cities numbered 1 to n

• Roads are bidirectional

• Use Dijkstra's algorithm

Sample Input/Output

4 5 1 4
1 2 10
1 3 5
2 3 2
2 4 1
3 4 9

8

Explanation

Optimal path: 1→3→2→4 with congestion 5+2+1=8. Alternative 1→2→4 has congestion 10+1=11.