// Priority Queue solution for Dijkstra's
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define MOD 1000000007
#define INF 1e18
#define N 10005
vector< vector<pi> > graph; // First is the vertex and Second is the weight
bool vis[N];
ll d[N];
void dijkstra(ll s) // s -> Source
{
fill(d, d + N, INF);
memset(vis, false, sizeof vis);
d[s] = 0;
priority_queue< pi, vector<pi>, less<pi> > q;
q.push(MP(d[s], s));
while(!q.empty())
{
pi temp = q.top();
q.pop();
ll u = temp.S;
//if(vis[u])
// continue;
// vis[u] = true;
for(vector<pi> :: iterator it = graph[u].begin(); it != graph[u].end(); it++)
{
ll v = it -> F;
ll wt = it -> S;
if(d[v] > d[u] + wt)
{
d[v] = d[u] + wt;
q.push( MP(d[v], v) );
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
ll t;
ll n, m, a, b, w;
ll i;
cin >> t;
while(t--)
{
cin >> n >> m;
graph.clear();
graph.resize(n + 2);
for(i = 0; i < m; i++)
{
cin >> a >> b >> w;
a--;
b--;
graph[a].PB(MP(b, w));
// graph[b].PB({a, w});
}
cin >> a >> b;
a--;
b--;
dijkstra(a);
ll ans = d[b];
if(ans == INF)
cout << "NO" << endl;
else
cout << ans << endl;
}
return 0;
}
Ly8gUHJpb3JpdHkgUXVldWUgc29sdXRpb24gZm9yIERpamtzdHJhJ3MgCgojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnR5cGVkZWYgbG9uZyBsb25nIGxsOwp0eXBlZGVmIHBhaXI8bGwsIGxsPiBwaTsKCiNkZWZpbmUgTVAgbWFrZV9wYWlyCiNkZWZpbmUgUEIgcHVzaF9iYWNrCiNkZWZpbmUgRiBmaXJzdAojZGVmaW5lIFMgc2Vjb25kCiNkZWZpbmUgTU9EIDEwMDAwMDAwMDcKI2RlZmluZSBJTkYgMWUxOAojZGVmaW5lIE4gMTAwMDUKCnZlY3RvcjwgdmVjdG9yPHBpPiA+IGdyYXBoOyAvLyBGaXJzdCBpcyB0aGUgdmVydGV4IGFuZCBTZWNvbmQgaXMgdGhlIHdlaWdodApib29sIHZpc1tOXTsKbGwgZFtOXTsKCnZvaWQgZGlqa3N0cmEobGwgcykgLy8gcyAtPiBTb3VyY2UKewoJZmlsbChkLCBkICsgTiwgSU5GKTsKCW1lbXNldCh2aXMsIGZhbHNlLCBzaXplb2YgdmlzKTsKCWRbc10gPSAwOwoJcHJpb3JpdHlfcXVldWU8IHBpLCB2ZWN0b3I8cGk+LCBsZXNzPHBpPiA+IHE7CglxLnB1c2goTVAoZFtzXSwgcykpOwoJd2hpbGUoIXEuZW1wdHkoKSkKCXsKCQlwaSB0ZW1wID0gcS50b3AoKTsKCQlxLnBvcCgpOwoJCWxsIHUgPSB0ZW1wLlM7CgkJLy9pZih2aXNbdV0pCgkvLwkJY29udGludWU7CgkvLwl2aXNbdV0gPSB0cnVlOwoJCWZvcih2ZWN0b3I8cGk+IDo6IGl0ZXJhdG9yIGl0ID0gZ3JhcGhbdV0uYmVnaW4oKTsgaXQgIT0gZ3JhcGhbdV0uZW5kKCk7IGl0KyspCgkJewoJCQlsbCB2ID0gaXQgLT4gRjsKCQkJbGwgd3QgPSBpdCAtPiBTOwoJCQlpZihkW3ZdID4gZFt1XSArIHd0KQoJCQl7CgkJCQlkW3ZdID0gZFt1XSArIHd0OwoJCQkJcS5wdXNoKCBNUChkW3ZdLCB2KSApOwoJCQl9CgkJfQoJfQp9CgppbnQgbWFpbigpCnsKCWlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKCWxsIHQ7CglsbCBuLCBtLCBhLCBiLCB3OwoJbGwgaTsKCWNpbiA+PiB0OwoJd2hpbGUodC0tKQoJewoJCWNpbiA+PiBuID4+IG07CgkJZ3JhcGguY2xlYXIoKTsKCQlncmFwaC5yZXNpemUobiArIDIpOwoJCWZvcihpID0gMDsgaSA8IG07IGkrKykKCQl7CgkJCWNpbiA+PiBhID4+IGIgPj4gdzsKCQkJYS0tOwoJCQliLS07CgkJCWdyYXBoW2FdLlBCKE1QKGIsIHcpKTsKCQkJLy8gZ3JhcGhbYl0uUEIoe2EsIHd9KTsKCQl9CgkJY2luID4+IGEgPj4gYjsKCQlhLS07CgkJYi0tOwoJCWRpamtzdHJhKGEpOwoJCWxsIGFucyA9IGRbYl07CgkJaWYoYW5zID09IElORikKCQkJY291dCA8PCAiTk8iIDw8IGVuZGw7CgkJZWxzZQoJCQljb3V0IDw8IGFucyA8PCBlbmRsOwoJfQoJcmV0dXJuIDA7Cn0K