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

Được gửi lên bởi:Jimmy
Ngày:2009-01-04
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:ACM Regional, HCMC 2008 Tic Tac Toe

hide comments
2021-05-27 18:04:02
Tham khảo: https://vnspoj.github.io/problems/TRAFFICN
2021-03-24 16:33:39
ez
2020-07-25 06:22:33
Thk cmt ngay dưới bị điên
2020-07-25 06:20:59
nhật hào bẩn
2020-05-03 09:41:07
xin gợi ý ạ. Em mới học ijk
2020-03-11 18:57:20
AC nhé thằng _spontaneously_
2020-03-11 17:53:16
_spontaneously_
Trâu đéo AC bọn l
2019-09-23 05:03:58
13 đấm mới AC :<. Đừng lưu LLONG_MAX bị WA á
2019-08-01 11:36:42
trau AC
2019-07-29 10:51:09


Last edit: 2019-07-29 11:46:35
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.