TRAFFICN  Traffic Network
https://codeforces.com/group/FLVn1Sc504/contest/274566/problem/N
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
varunsainii:
20201018 06:54:53
One of the most beautiful question Last edit: 20201018 06:55:14 

lucifer98:
20200817 09:12:29
I am getting a TLE which using dijkstra ,anyone can help 

utkarsh_bansal:
20200801 13:22:51
it is atmost one twoway road 

einsdurchnull:
20200713 18:34:47
Thank you, it was fun 

sarthak_19:
20200710 15:43:14
Nice ques on dijkstra 

hellboy41:
20200626 19:36:32
getting TLE while using dijkstra with priority queue k (number of twoway edges) times 

pumping_iron:
20200526 07:45:25
nice application of dijkstra, though a easy question Last edit: 20200526 07:45:38 
Added by:  Jimmy 
Date:  20090104 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ACM Regional, HCMC 2008 Tic Tac Toe 