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

#define __DEBUG
#ifdef __DEBUG
    #define print_pair(p) do{std::cout << "(" << ((p).first) << ", "\
                            << ((p).second) << ")" << std::endl;}while(0);
#endif

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);
    distances.resize(vertexes, INF);
    path.resize(vertexes, -1);
}

void Graph::input()
{
#ifdef __DEBUG
    std::cout << "default distances:" << std::endl;
    for (auto &i : distances)
        std::cout << i << " ";
    std::cout << std::endl;
#endif
    int start = 0, end = 0, length = 0;
    for (int i = 0; i < edges_count; ++i)
    {
        std::cin >> start >> end >> length;
        adj[start - 1].push_back (std::make_pair(length, end - 1));
    }
#ifdef __DEBUG
    std::cout << "adjacency lists:" << std::endl;
    for (int i = 0; i < adj.size(); ++i)
    {
        for (int j = 0; j < adj[i].size(); ++j)
        {
            std::cout << "(" << i << ", " << (adj[i][j].second) << ")" << std::endl;
        }
        std::cout << std::endl;
    }
#endif
}

Graph::result
Graph::dijkstra (int start)
{
#ifdef __DEBUG
    std::cout << "Dijkstra algorithm tracing:" << std::endl;
#endif
    distances[start - 1] = 0;
    std::set<std::pair<int, int>> q;
    q.insert (std::make_pair(distances[start - 1], start - 1));
    while (!q.empty())
    {
#ifdef __DEBUG
        std::cout << "top element of a set: ";
        print_pair(*q.begin());
#endif
        int current = q.begin()->second;
        q.erase(q.begin());
#ifdef __DEBUG
    std::cout << "current vertex: " << current << std::endl;
#endif
        for (int i = 0; i < adj[current].size(); ++i)
        {
#ifdef __DEBUG
    std::cout << "current vertex: " << current;
    std::cout << " and current state of distances array is: " << std::endl;
    for (auto i: distances)
        std::cout << i << " ";
    std::cout << std::endl;
#endif
            int to = adj[current][i].second;
            int length = adj[current][i].first;
            // Relaxations
            if (distances[to] > distances[current] + length)
            {
#ifdef __DEBUG
    std::cout << "relaxation for edge (" << current << ", " << to << ") ";
    std::cout << "with weight " << length << std::endl;
#endif
                
                q.erase(std::make_pair(distances[to], to));
                distances[to] = distances[current] + length;
                path[to] = current;
                q.insert(std::make_pair(distances[to], to));
            }
        }
    }
    // Replace INF by -1
    std::replace (distances.begin(), distances.end(), INF, -1);
    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;
}