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
hung:
20161019 10:43:01
use heap and fast i/o ac with 0.01 s :)


levim:
20161018 21:49:32
Nice problem :) 

ahmed Ibrahim:
20160811 12:43:36
i 'm really happy ,finally AC after many of WA & TLE ,I like this problem,it has a lot of knowledge & special cases <3 <3 <3 :D :D :D 

Anuj Arora:
20160801 13:11:25
I can't believe it.....AC in one attempt.....made 1 assumption and submitted code....still got accepted Last edit: 20160801 13:11:37 

iharsh234:
20160708 15:30:41
2 times dijkstra..Nice Problem Last edit: 20160708 15:30:57 

surayans tiwari(http://bit.ly/1EPzcpv):
20160704 20:44:00
don't just blindly take 1061109567 , u can take any value greater than 200000000 because the maximum value of cost can reach 100000*1000 = 100000000 so to be on safe side take value greater than 200000000 , i took 300000000 and got ac! 

aspro:
20160622 06:29:50
nice question.....comments helped Last edit: 20160622 06:30:22 

ajay_5097:
20160603 17:26:58
WTF .. Used INT_MAX got Too many WAs


danuwfna:
20160602 15:19:00
@ankurverma1994 it's not weird, because without calculated value for INF, at every iteration you make an computation. 

ankurverma1994:
20160529 13:57:44
Using Integer.MAX_VALUE/3 as infinity getting TLE. But putting infinity as calculated value of Integer.MAX_VALUE/3 getting AC in Java. Something weird. :( 
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 