TRAFFICN - Traffic Network

### 题意简述 给你一个 $n$ 个点的图，其中有 $m$ 条有向边和**待加入的** $k$ 条无向边，现在可以任选**一条**无向边，请你求出从 $s$ 点到 $t$ 点的最短路长度。 ### 输入格式 第 $1$ 行一个整数 $T$ 表示数据组数。 对于每组数据： 第 $1$ 行五个整数 $n,m,k,s,t$。 接下来 $m$ 行，每行三个整数 $u,v,w$ 表示有一条从 $u$ 到 $v$ 长度为 $w$ 的有向边。 接下来 $k$ 行，每行三个整数 $u,v,w$ 表示有一条从 $u$ 到 $v$ 长度为 $w$ 的无向边。 ### 输出格式 共 $T$ 行，每行一个整数表示该图从 $s$ 点到 $t$ 点的最短路长度，若不能从 $s$ 点到 $t$ 点，输出 $-1$。 ### 数据范围 对于 $100\%$ 的数据，$1\le T\le20\text{，}n\le10000\text{，}m\le100000\text{，}k<300\text{，}1\le s,t,u,v\le n\text{，}1\le w\le1000$。

[English](/problems/TRAFFICN/en/) [Vietnamese](/problems/TRAFFICN/vn/) 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.

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.

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.

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

35