Balanced Amusement Park Journey

Big Zhongfeng is at an amusement park with \( n \) attractions connected by \( m \) bidirectional roads. Every road takes a certain amount of time to traverse. Each attraction is accompanied by a shop that sells either coke or hamburgers.

Since Big Zhongfeng is very fond of food, whenever he arrives at an attraction, he will first purchase and consume either a coke or a hamburger before doing anything else. However, if at any point the number of hamburgers he has eaten exceeds the number of cokes he has drunk by more than \( k \) (i.e. if \( H - C > k \)), he will feel very thirsty. Similarly, if the number of cokes exceeds the number of hamburgers by more than \( k \) (i.e. if \( C - H > k \)), he will feel very hungry.

Big Zhongfeng is currently at attraction \( a \) and wants to go to attraction \( b \). He wants to plan his journey so that he never feels too thirsty or too hungry along the way. Note that at both the starting and destination attractions he also makes a purchase. Determine the minimum total travel time required to go from \( a \) to \( b \) such that there exists a valid purchasing strategy at each attraction that keeps the absolute difference \( |H-C| \) within \( k \) at all times. If no such journey exists, output -1.

inputFormat

The first line contains five integers \( n, m, k, a, b \) where \( n \) is the number of attractions, \( m \) is the number of roads, \( k \) is the allowed imbalance, \( a \) is the starting attraction index, and \( b \) is the destination attraction index.

The next \( m \) lines each contain three integers \( u, v, t \) indicating that there is a bidirectional road between attractions \( u \) and \( v \) taking \( t \) time units to travel.

outputFormat

Output a single integer: the minimum total travel time from attraction \( a \) to \( b \) such that Big Zhongfeng can always make a valid purchase (either coke or hamburger) at every attraction and never have \( |H-C| > k \). If no valid journey exists, output -1.

sample

3 3 1 1 3
1 2 2
2 3 2
1 3 5

4