TRAFFICN  Traffic Network
English  Vietnamese 
The city traffic network consists of n nodes numbered from 1 to n and m oneway 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 twoway roads are proposed as candidates to be constructed. Your task is to write a program to choose one twoway 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 oneway 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 twoway 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 twoway 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
s_a_k_s_h_a_m:
20180708 18:48:10
a good problem


be1035016:
20180701 12:58:26
nice problem 

Bác Ba Phì:
20180630 05:57:33
2000 AC submissions, and only 5 of them are in Java. I think the time limit is way too strict for Java. 

shahi9935:
20180609 04:11:18
Thanku @ansh_gupta788 and @sherlock11 for your thoughts 

sherlock11:
20180413 18:48:37
the problem states that " use at most one road and not exactly one road"........this costed me 3 WA...


ansh_gupta788:
20180412 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:
20180401 11:52:20
Best Problem on dijkstra's algorithm that i have solved. 

hugo_go2308:
20180317 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:
20180313 13:47:38
if wrong ,check for no path condition:) 

vaibhav_1997:
20171026 08:41:06
how can the shortest path from any random node to target node be calculated by reversing the edges and applying dikjstra

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