5.6 🗺️🚴♂️Dhrumil's City Bike Quest 🏙️🚲

Score: 25pts

Time Limit: 5.00 sec

There are n cities in your country, numbered from 1 to n

You are currently on city 1 and want to reach city n

Each city has a bike which has a weight of x[i] kg

Lets say the distance between 2 nodes is 5, then you will require 5 * x[i] seconds to travel.

You can choose to either continue with a bike u already have, or choose a new bike from the city.

You are given m edges, bidirectional roads

Find the minimum time to reach nth city

You are currently on city 1 and want to reach city n

Each city has a bike which has a weight of x[i] kg

Lets say the distance between 2 nodes is 5, then you will require 5 * x[i] seconds to travel.

You can choose to either continue with a bike u already have, or choose a new bike from the city.

You are given m edges, bidirectional roads

Find the minimum time to reach nth city

Constraints

All values are Integers(10^9)

Input Format

First Line: An integer T representing the number of test cases.

For Each Test Case:

First Line: Three integers n (number of cities), m (number of bidirectional roads), and b (maximum weight of a bike).

Second Line: An array of n integers x[i] representing the weights of bikes in each city.

Next m Lines: Each line contains three integers representing a road between source(u) and destination(v) with distance d.

For Each Test Case:

First Line: Three integers n (number of cities), m (number of bidirectional roads), and b (maximum weight of a bike).

Second Line: An array of n integers x[i] representing the weights of bikes in each city.

Next m Lines: Each line contains three integers representing a road between source(u) and destination(v) with distance d.

Output Format

The output numbers correspond to the minimum time taken to reach city n from source city in each test case.

Example 1

Input:

1

5 5

1 2 2

3 2 1

2 4 5

2 5 7

4 5 1

5 2 1 3 3

Output:

19

Explanation:

n=5, m=5

Edge from 1->2 distance = 2

Edge from 3->2 distance = 1

Edge from 2->4 distance = 5

Edge from 2->5 distance = 7

Edge from 4->5 distance = 1

The bike weights of each node respectively are 5, 2, 1, 3, 3

The optimal way is go from 1 to 2 with bike 1 => 10s time

Then take bike 2 with weight = 2, then go from 2 to 3 => 2s time

Then take bike 3 with weight = 1, then go from 3 to 2 => 1s time

Now go from 2 to 4 with the same bike => 5s time

Then go to 4 to 5 => 1s time

Total = 19s time

1

5 5

1 2 2

3 2 1

2 4 5

2 5 7

4 5 1

5 2 1 3 3

Output:

19

Explanation:

n=5, m=5

Edge from 1->2 distance = 2

Edge from 3->2 distance = 1

Edge from 2->4 distance = 5

Edge from 2->5 distance = 7

Edge from 4->5 distance = 1

The bike weights of each node respectively are 5, 2, 1, 3, 3

The optimal way is go from 1 to 2 with bike 1 => 10s time

Then take bike 2 with weight = 2, then go from 2 to 3 => 2s time

Then take bike 3 with weight = 1, then go from 3 to 2 => 1s time

Now go from 2 to 4 with the same bike => 5s time

Then go to 4 to 5 => 1s time

Total = 19s time