#include <climits>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>

class Graph
{
private:
    std::vector<std::vector<std::pair<int, int>>> adj;
    std::vector<int> distances;
    std::vector<int> path;
    const int INF = INT_MAX;
    int vertexes_count = 0, edges_count = 0;
    void relax (int start, int end, int length);
public:
    typedef std::vector<int> result;
    Graph();
    Graph(int vertexes, int edges);
    ~Graph();
    void input();
    void output();
    result dijkstra(int start);
};

Graph::Graph() {}

Graph::~Graph() {}

Graph::Graph(int vertexes, int edges)
{
    vertexes_count = vertexes;
    edges_count    = edges;
    adj.resize(vertexes + 1);
    distances.resize(vertexes + 1, INF);
    path.resize(vertexes + 1, -1);
}

void Graph::input()
{
    int start = 0, end = 0, length = 0;
    for (int i = 0; i < edges_count; ++i)
    {
        std::cin >> start >> end >> length;
        adj[start].push_back (std::make_pair(length, end));
        adj[end].push_back (std::make_pair(length, start));
    }
}

Graph::result
Graph::dijkstra (int start)
{
    distances[start] = 0;
    path[start] = start;
    std::priority_queue<std::pair<int, int>,
                        std::vector<std::pair<int, int>>,
                        std::greater<std::pair<int, int>>> q;
    q.push(std::make_pair(0, start));
    while (!q.empty())
    {
        int current = q.top().second;
        int len     = q.top().first;
        q.pop();
        for (int i = 0; i < adj[current].size(); ++i)
        {
            int to     = adj[current][i].second;
            int length = adj[current][i].first;
            // Relaxations
            if (distances[to] > distances[current] + length)
            {
                path[to] = current;     
                distances[to] = distances[current] + length;
                q.push(std::make_pair(distances[to], to));
            }
        }
    }
    // Replace INF by -1
    //std::replace (distances.begin(), distances.end(), INF, -1);
    for (auto i : distances)
        std::cout << i << " ";
    std::cout << std::endl;
    return distances;
}

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