Minimizing Caesar's Dissatisfaction

After Caesar's victorious expedition in Gaul, he returned full of praises. He even visited Genoa personally to inspect the flourishing city. Under your guidance, Genoa has prospered, and with increased treasury revenue, you built a transportation network. The ancient Roman system consists of two types of roads: Rome Road and Dirt Road. Between any two intersections, there is exactly one type of road. On a Rome Road, a carriage can be driven, whereas on a Dirt Road it cannot. Due to the enormous cost of building roads, it is impossible to connect the entire city using only Rome Roads.

Caesar, who has reached the port, now wishes to tour your residence. Owing to his peculiar taste, he prefers riding in a carriage over walking. Hence, his dissatisfaction when traveling on a Dirt Road is higher than when he travels on a Rome Road.

Your task is to design a route from the starting intersection (the port) to your home (the destination) that minimizes Caesar's total dissatisfaction.

The city is modeled as an undirected weighted graph with N intersections and M roads. The input provides two extra integers R and D which denote the dissatisfaction values when traversing a Rome Road and a Dirt Road respectively (R < D). Each road is described by three integers u, v and t, where u and v are the intersection indices and t specifies the road type (0 for Rome Road, 1 for Dirt Road). The cost to traverse a road is given by:

$\text{cost} = \begin{cases} R, & \text{if } t = 0, \\ D, & \text{if } t = 1. \end{cases}$

Compute the minimum total dissatisfaction along a path from the start intersection S to the destination intersection T. If there is no path, output -1.

inputFormat

The first line contains six space-separated integers: N M S T R D, where N is the number of intersections, M is the number of roads, S is the starting intersection (the port), T is the destination (your home), R is the dissatisfaction for using a Rome Road, and D is the dissatisfaction for using a Dirt Road (with R < D).

Each of the following M lines contains three integers u v t describing a road between intersections u and v. Here, t is 0 for a Rome Road and 1 for a Dirt Road. The graph is undirected; each road can be used in both directions.

outputFormat

Output a single integer representing the minimum total dissatisfaction incurred along the path from S to T. If there is no valid path, output -1.

sample

4 4 1 4 1 3
1 2 0
2 3 1
3 4 0
1 4 1

3