#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Graph
{
private:
    // Pair: (ending vertex, weigth)
    vector<vector<pair<int, int>>> adj_list;
    int nodes, edges;
public:
    Graph() = default;
    Graph(int nodes, int edges);
    Graph(int nodes, int edges, istream &is);
    ~Graph(){}
    void print_edges();
    std::vector<int> dijkstra(int);
};

Graph::Graph (int nodes, int edges)
{
    adj_list.resize (nodes + 1);
    this->nodes = nodes;
    this->edges = edges;
}

Graph::Graph(int nodes, int edges, istream &is) : Graph(nodes, edges)
{
    int begin = 0, end = 0, weigth = 0;
    for (size_t i = 0; i < edges; ++i)
    {
        is >> begin >> end >> weigth;
        adj_list[begin].push_back (make_pair(end, weigth));
        adj_list[end].push_back (make_pair(begin, weigth));
    }
}

void Graph::print_edges()
{
    for (size_t i = 0; i < adj_list.size(); ++i)
    {
        for (size_t j = 0; j < adj_list[i].size(); ++j)
        {
            cout << "(" << i << ", " << adj_list[i][j].first << ")";   // (i, j)
            cout << " ";
        }
        cout << endl;
    }
}

std::vector<int> Graph::dijkstra(int start)
{
    const int INF = 1000000000;
    vector<int>  distance (nodes + 1, INF);
    vector<bool> visited (nodes + 1);
    
    distance[start] = 0;
    for (int i = 1; i <= nodes; ++i)
    {
        // Find a vertex with minimal mark
        int minimum = INF;
        int current = 0;
        for (int j = 1; j <= nodes; ++j)
        {
            if (distance[j] < minimum && !visited[j])
            {
                minimum = distance[j];
                current = j;
            }
        }
        // Mark minimal node as visited
        visited[current] = true;
        // Relaxations
        for (int i = 0; i < adj_list[current].size(); ++i)
        {
            int to     = adj_list[current][i].first;
            int weigth = adj_list[current][i].second;
            distance[to] = std::min (distance[to], distance[current] + weigth);
        }
    }
    
    return distance;
}

int main() {
    int tests = 0, nodes = 0, edges = 0, start = 0;
    cin >> tests;
    
    for (int i = 0; i < tests; ++i)
    {
        cin >> nodes >> edges;
        Graph g(nodes, edges, cin);
        cin >> start;
        auto result = g.dijkstra (start);
        for (int i = 1; i < result.size(); ++i)
        {
            if (i != start)
                cout << result[i] << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}