#include<iostream>
    #include<vector>
    #include<queue>

    using namespace std;

    const int inf=2009000999;

    int main(){
        int num;
        cin >> num;
        for(int g=0;g<num;++g){
            int n,m;
            cin >> n >> m;
            vector< vector< pair<int,int> > > graph(n);
            for(int i=0;i<m;++i){
                int t1,t2,t3;
                cin >> t1 >> t2 >> t3;
                graph[t1].push_back({t3,t2});
                graph[t2].push_back({t3,t1});
            }
            int start;
            cin >> start;

            priority_queue< pair<int,int> > q;
            vector<int> len(n,inf);
            len[start]=0;
            q.push({0,start});
            while(!q.empty()){
                pair<int,int> tmp=q.top();
                q.pop();
                if(-tmp.first>len[tmp.second])
                    continue;
                for(int i=0;i<graph[tmp.second].size();++i)
                    if(len[tmp.second]+graph[tmp.second][i].first<len[graph[tmp.second][i].second]){
                        q.push({-len[tmp.second]-graph[tmp.second][i].first,graph[tmp.second][i].second});
                        len[graph[tmp.second][i].second]=len[tmp.second]+graph[tmp.second][i].first;
                    }
            }
            for(int i=0;i<n;++i)
                cout << len[i] << ' ';
            cout << endl;
        }
    }