dijkstra

#include <stdio.h>
#include <bits/stdc++.h>
//%lld
typedef long long ll;
#define si(a) scanf("%d", &a)
#define sii(a, b) scanf("%d%d", &a, &b)
#define pi(a) printf("%d\n", a)

using namespace std;
struct par{
    int v;
    int t;
};

vector<par>grafo[100005];
bool marcado[100005];
int pai[100005];
int custo[100005];

int main(){
    priority_queue<int, vector<int>, greater<int> > fila;
    int n, m, c, f, t, a, b;
    si(t);
    while(t--){
        memset(pai, -1, sizeof(pai));
        memset(marcado, false, sizeof(marcado));
        memset(grafo, 0, sizeof(grafo));
        fill(custo, custo+100005, 100005);
        scanf("%d%d%d%d", &n, &m, &c, &f);
        for(int i = 0;i<m;i++){
            sii(a, b);
            int peso;
            si(peso);
            par aux;
            aux.v= b;
            aux.t = peso;
            grafo[a].push_back(aux);
            aux.v= a;
            aux.t = peso;
            grafo[b].push_back(aux);
        }
        fila.push(c);
        marcado[c] = true;
        custo[c] = 0;
        pai[c] = 0;
        while(!fila.empty()){
            int aux = fila.top();
            fila.pop();
            marcado[aux] = true;
            for(int i = 0;i<(grafo[aux].size());i++){
                if(!marcado[grafo[aux][i].v]){
                        pai[grafo[aux][i].v] = aux;
                        custo[grafo[aux][i].v] = min(custo[grafo[aux][i].v],(grafo[aux][i].t)+custo[pai[grafo[aux][i].v]]);
                        fila.push(grafo[aux][i].v);
                }
            }
        }
        if(marcado[f])pi(custo[f]);
        else puts("NONE");
    }
}