#include <cstdio> #include <vector> #include <queue> #define MAX 10005 #define INF 1000000000 using namespace std; vector< vector< pair<int, int> > > graph(MAX); int dist[MAX]; priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq; void add(int u, int v, int w) { graph[u].push_back( make_pair(v, w) ); } void clear() { for (int i = 0; i < MAX; i++) graph[i].clear(); } int main() { int T, u, v, w, A, B, minDist, minNode, n, m, N, W; pair<int, int> t; scanf("%d", &T); for (int k = 1; k <= T; k++) { clear(); scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d%d%d", &u, &v, &w); add(u, v, w); } scanf("%d%d", &A, &B); for (int i = 1; i <= n; i++) dist[i] = INF; dist[A] = 0; pq.push( make_pair( 0, A ) ); while (!pq.empty()) { t = pq.top(); pq.pop(); minNode = t.second; minDist = t.first; if ( dist[ minNode ] != minDist ) continue; if (minNode == B) break; for (int i = 0; i < graph[ minNode ].size(); i++) { N = graph[ minNode ][i].first; W = graph[ minNode ][i].second; if ( dist[N] > dist[ minNode ] + W ) { dist[N] = dist[ minNode ] + W; pq.push( make_pair( dist[N], N ) ); } } } if (dist[B] == INF) printf("NO\n"); else printf("%d\n", dist[B]); } return 0; }