#include<iostream>
#include<cstdio>
#include<vector>
#include<utility>
#include<queue>
#include<climits>
using namespace std;
typedef pair<int,int> pi;
typedef vector<pi> pii;
main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,high,from,to;
        scanf("%d%d%d%d",&n,&high,&from,&to);
        vector<pii> adj(n+1);
        for(int i=0;i<high;i++)
        {
            int s,e,dist;
            scanf("%d%d%d",&s,&e,&dist);
            adj[s].push_back(pi(e,dist));
        }
        vector<int> dist(n+1,INT_MAX);
        dist[from]=0;
        priority_queue< pi,pii,greater<pi> > q;
        q.push(pi(0,from));
        while(!q.empty())
        {
            pi my=q.top();
            q.pop();
            int cv=my.second,cd=my.first;
            if(cv==to)
                break;
            if(cd<=dist[cv])
            {
                for(int i=0;i<adj[cv].size();i++)
                {
                    int nv=adj[cv][i].second,nd=adj[cv][i].first;
                    if(dist[nv]>nd+dist[cv])
                    {
                        dist[nv]=nd+dist[cv];
                        q.push(pi(dist[nv],nv));
                    }
                }
            }
        }
        for(int i=0;i<dist.size();i++)
            cout<<dist[i]<<" ";
        if(dist[to]==INT_MAX)
            cout<<"NONE\n";
        else
            cout<<dist[to]<<"\n";

    }
}