#include<bits/stdc++.h>
using namespace std;


class Graph{
    unordered_map<int, list<pair<int,int> > > m;
    
public:

    void addEdge(int u,int v,int dist,bool bidir=true){
        m[u].push_back(make_pair(v,dist)); 
        if(bidir){
            m[v].push_back(make_pair(u,dist));
        }
        
    }
    void printAdj(){
        //Let try to print the adj list
        //Iterate over all the key value pairs in the map 
        for(auto j:m){
            
            cout<<j.first<<"->";
            
            //Iterater over the list of cities
            for(auto l: j.second){
                    cout<<"("<<l.first<<","<<l.second<<")";
                
            }
            cout<<endl;
        }
    
    }

	void dijkastraSSSP(int V ,int src){

		unordered_map<int,int> dist;
        
        //Set all distance to infinity
        for(auto j:m){
            dist[j.first] = INT_MAX;
        }
		//pair is of dist anf node
		set<pair<int , int> > s;

		s.insert(make_pair(0 , src));

		while(!s.empty()){

			pair<int, int> tmp = *(s.begin());
			//removing this pair  
        	s.erase(s.begin()); 
			int node = tmp.second;
			int dist_curr = tmp.first;

			//now going through the neighbours of this node
			for(auto neighbours :m[node]){

				if(dist_curr + neighbours.second <dist[neighbours.first] ){
					
					int dest = neighbours.first;
					auto f = s.find( make_pair(dist[dest],dest));
                    if(f!=s.end()){
                        s.erase(f);
                    }
                    
                    //Insert the new pair
                    dist[dest] = dist_curr + neighbours.second;
                    s.insert(make_pair(dist[dest],dest));
                    
                }
                
            }
        }
        //Lets print distance to all other node from src
        for(auto d:dist){
            
            cout<<d.second<<" ";
        }
	}
};


int main(){

    
    int t=0;
	cin>>t;
	while(t--){
    Graph g;
	int n , m;
	cin>>n>>m;

	for(int i =0;i<m;i++){
    	int x=0 , y=0 , dist=0;
		cin>>x>>y>>dist;
		g.addEdge(x , y , dist);
	}
	int s;
	cin>>s;
    //g.printAdj();
   	g.dijkastraSSSP(s , n);
	}
}