TRAFFICN - Traffic Network


The city traffic network consists of n nodes numbered from 1 to n and m one-way roads connecting pairs of nodes. In order to reduce the length of the shortest path between two different critical nodes s and t, a list of k two-way roads are proposed as candidates to be constructed. Your task is to write a program to choose one two-way road from the proposed list in order to minimize the resulting shortest path between s and t.

Input

The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.

For each data set, the first line contains five positive integers n (n ≤ 10 000), m (m ≤ 100 000), k (k < 300), s (1 ≤ s ≤ n), t (1 ≤ t ≤ n) separated by space. The ith line of the following m lines contains three integers di, ci, li separated by space, representing the length li ( 0< li ≤ 1000) of the ith one-way road connecting node di to ci. The jth line of the next k lines contains three positive integers uj, vj and qj (qj ≤ 1000) separated by space, representing the jth proposed two-way road of length qj connecting node uj to vj.

Output

For each data set, write on one line the smallest possible length of the shortest path after building the chosen one two-way road from the proposed list. In case, there does not exist a path from s to t, write -1.

Example

Sample Input
1
4 5 3 1 4
1 2 13
2 3 19
3 1 25
3 4 17
4 1 18
1 3 23
2 3 5
2 4 25	

Sample Output
35

hide comments
sherlock11: 2018-04-13 18:48:37

the problem states that " use at most one road and not exactly one road"........this costed me 3 WA...
this is very nice problem on diJkstra...HAPPY CODING!!!!!!

Last edit: 2018-04-14 11:09:51
ansh_gupta788: 2018-04-12 21:41:08

When i tried it for the first time , it seemed to be a very hard problem . But now when i tried after a month , I did it in the very first attempt :)

racse: 2018-04-01 11:52:20

Best Problem on dijkstra's algorithm that i have solved.

hugo_go2308: 2018-03-17 20:09:10

I have solved this issue on C++, but the same algorithm does not work with Java. I got a runtime error (NZEC). Have an idea that reason in the reader from the console. may I ask you how you read data from console by java? Thank you in advance

chetan4060: 2018-03-13 13:47:38

if wrong ,check for no path condition:)

vaibhav_1997: 2017-10-26 08:41:06

how can the shortest path from any random node to target node be calculated by reversing the edges and applying dikjstra

sharif ullah: 2017-09-26 17:00:28

WA???
check these out
1. when i use INFINITY for upper value for calculating distance give wrong ans
2.when use cin,cout gives TLE so.uz fast i/o
3.while conntection a path with an edge onsider two case (a->b) && (b->a) (2 dijikstra approach)!!!!

sonudoo: 2017-06-19 17:57:47

A single dijkstra may also do. All you have to do is to create two graphs and the new roads will connect these two graphs.

Thotsaphon Thanatipanonda: 2017-06-04 06:23:04

length li or qj > 1000. It waste my time.

babur: 2017-05-26 08:40:45

Truely Classic...Twice dijkstra once straight and then reverse..


Added by:Duc
Date:2009-01-04
Time limit:0.140s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM Regional, Ho Chi Minh City 2008