#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;
}

I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNsYXNzIEdyYXBoCnsKcHJpdmF0ZToKICAgIC8vIFBhaXI6IChlbmRpbmcgdmVydGV4LCB3ZWlndGgpCiAgICB2ZWN0b3I8dmVjdG9yPHBhaXI8aW50LCBpbnQ+Pj4gYWRqX2xpc3Q7CiAgICBpbnQgbm9kZXMsIGVkZ2VzOwpwdWJsaWM6CiAgICBHcmFwaCgpID0gZGVmYXVsdDsKICAgIEdyYXBoKGludCBub2RlcywgaW50IGVkZ2VzKTsKICAgIEdyYXBoKGludCBub2RlcywgaW50IGVkZ2VzLCBpc3RyZWFtICZpcyk7CiAgICB+R3JhcGgoKXt9CiAgICB2b2lkIHByaW50X2VkZ2VzKCk7CiAgICBzdGQ6OnZlY3RvcjxpbnQ+IGRpamtzdHJhKGludCk7Cn07CgpHcmFwaDo6R3JhcGggKGludCBub2RlcywgaW50IGVkZ2VzKQp7CiAgICBhZGpfbGlzdC5yZXNpemUgKG5vZGVzICsgMSk7CiAgICB0aGlzLT5ub2RlcyA9IG5vZGVzOwogICAgdGhpcy0+ZWRnZXMgPSBlZGdlczsKfQoKR3JhcGg6OkdyYXBoKGludCBub2RlcywgaW50IGVkZ2VzLCBpc3RyZWFtICZpcykgOiBHcmFwaChub2RlcywgZWRnZXMpCnsKICAgIGludCBiZWdpbiA9IDAsIGVuZCA9IDAsIHdlaWd0aCA9IDA7CiAgICBmb3IgKHNpemVfdCBpID0gMDsgaSA8IGVkZ2VzOyArK2kpCiAgICB7CiAgICAgICAgaXMgPj4gYmVnaW4gPj4gZW5kID4+IHdlaWd0aDsKICAgICAgICBhZGpfbGlzdFtiZWdpbl0ucHVzaF9iYWNrIChtYWtlX3BhaXIoZW5kLCB3ZWlndGgpKTsKICAgICAgICBhZGpfbGlzdFtlbmRdLnB1c2hfYmFjayAobWFrZV9wYWlyKGJlZ2luLCB3ZWlndGgpKTsKICAgIH0KfQoKdm9pZCBHcmFwaDo6cHJpbnRfZWRnZXMoKQp7CiAgICBmb3IgKHNpemVfdCBpID0gMDsgaSA8IGFkal9saXN0LnNpemUoKTsgKytpKQogICAgewogICAgICAgIGZvciAoc2l6ZV90IGogPSAwOyBqIDwgYWRqX2xpc3RbaV0uc2l6ZSgpOyArK2opCiAgICAgICAgewogICAgICAgICAgICBjb3V0IDw8ICIoIiA8PCBpIDw8ICIsICIgPDwgYWRqX2xpc3RbaV1bal0uZmlyc3QgPDwgIikiOyAgIC8vIChpLCBqKQogICAgICAgICAgICBjb3V0IDw8ICIgIjsKICAgICAgICB9CiAgICAgICAgY291dCA8PCBlbmRsOwogICAgfQp9CgpzdGQ6OnZlY3RvcjxpbnQ+IEdyYXBoOjpkaWprc3RyYShpbnQgc3RhcnQpCnsKICAgIGNvbnN0IGludCBJTkYgPSAxMDAwMDAwMDAwOwogICAgdmVjdG9yPGludD4gIGRpc3RhbmNlIChub2RlcyArIDEsIElORik7CiAgICB2ZWN0b3I8Ym9vbD4gdmlzaXRlZCAobm9kZXMgKyAxKTsKICAgIAogICAgZGlzdGFuY2Vbc3RhcnRdID0gMDsKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG5vZGVzOyArK2kpCiAgICB7CiAgICAgICAgLy8gRmluZCBhIHZlcnRleCB3aXRoIG1pbmltYWwgbWFyawogICAgICAgIGludCBtaW5pbXVtID0gSU5GOwogICAgICAgIGludCBjdXJyZW50ID0gMDsKICAgICAgICBmb3IgKGludCBqID0gMTsgaiA8PSBub2RlczsgKytqKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKGRpc3RhbmNlW2pdIDwgbWluaW11bSAmJiAhdmlzaXRlZFtqXSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgbWluaW11bSA9IGRpc3RhbmNlW2pdOwogICAgICAgICAgICAgICAgY3VycmVudCA9IGo7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgLy8gTWFyayBtaW5pbWFsIG5vZGUgYXMgdmlzaXRlZAogICAgICAgIHZpc2l0ZWRbY3VycmVudF0gPSB0cnVlOwogICAgICAgIC8vIFJlbGF4YXRpb25zCiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBhZGpfbGlzdFtjdXJyZW50XS5zaXplKCk7ICsraSkKICAgICAgICB7CiAgICAgICAgICAgIGludCB0byAgICAgPSBhZGpfbGlzdFtjdXJyZW50XVtpXS5maXJzdDsKICAgICAgICAgICAgaW50IHdlaWd0aCA9IGFkal9saXN0W2N1cnJlbnRdW2ldLnNlY29uZDsKICAgICAgICAgICAgZGlzdGFuY2VbdG9dID0gc3RkOjptaW4gKGRpc3RhbmNlW3RvXSwgZGlzdGFuY2VbY3VycmVudF0gKyB3ZWlndGgpOwogICAgICAgIH0KICAgIH0KICAgIAogICAgcmV0dXJuIGRpc3RhbmNlOwp9CgppbnQgbWFpbigpIHsKICAgIGludCB0ZXN0cyA9IDAsIG5vZGVzID0gMCwgZWRnZXMgPSAwLCBzdGFydCA9IDA7CiAgICBjaW4gPj4gdGVzdHM7CiAgICAKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgdGVzdHM7ICsraSkKICAgIHsKICAgICAgICBjaW4gPj4gbm9kZXMgPj4gZWRnZXM7CiAgICAgICAgR3JhcGggZyhub2RlcywgZWRnZXMsIGNpbik7CiAgICAgICAgY2luID4+IHN0YXJ0OwogICAgICAgIGF1dG8gcmVzdWx0ID0gZy5kaWprc3RyYSAoc3RhcnQpOwogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDwgcmVzdWx0LnNpemUoKTsgKytpKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKGkgIT0gc3RhcnQpCiAgICAgICAgICAgICAgICBjb3V0IDw8IHJlc3VsdFtpXSA8PCAiICI7CiAgICAgICAgfQogICAgICAgIHN0ZDo6Y291dCA8PCBzdGQ6OmVuZGw7CiAgICB9CiAgICByZXR1cm4gMDsKfQ==

MQoyMCA1NAoxIDcgNDUKMiAxNCAxNQozIDcgMjkKNCAxIDQ4CjUgMSA2Ngo2IDcgMTcKNyAxNCAxNQo4IDE0IDQzCjkgMSAyNwoxMCAxIDMzCjExIDE0IDY0CjEyIDE0IDI3CjEzIDcgNjYKMTQgNyA1NAoxNSAxNCA1NgoxNiA3IDIxCjE3IDEgMjAKMTggMSAzNAoxOSA3IDUyCjIwIDE0IDE0CjkgMTQgOQoxNSAxIDM5CjEyIDEgMjQKOSAxIDE2CjEgMiAzMwoxOCAxIDQ2CjkgMSAyOAoxNSAxNCAzCjEyIDEgMjcKMSAyIDUKMTUgMSAzNAoxIDIgMjgKOSA3IDE2CjMgNyAyMwo5IDcgMjEKOSAxNCAxOQozIDEgMjAKMyAxIDUKMTIgMTQgMTkKMyAxNCAyCjEyIDEgNDYKMyAxNCA1CjkgMTQgNDQKNiAxNCAyNgo5IDE0IDE2CjkgMTQgMzQKNiA3IDQyCjMgMTQgMjcKMSA3IDkKMSA3IDQxCjE1IDE0IDE5CjEyIDcgMTMKMyA3IDEwCjEgNyAyCjE3

1
20 54
1 7 45
2 14 15
3 7 29
4 1 48
5 1 66
6 7 17
7 14 15
8 14 43
9 1 27
10 1 33
11 14 64
12 14 27
13 7 66
14 7 54
15 14 56
16 7 21
17 1 20
18 1 34
19 7 52
20 14 14
9 14 9
15 1 39
12 1 24
9 1 16
1 2 33
18 1 46
9 1 28
15 14 3
12 1 27
1 2 5
15 1 34
1 2 28
9 7 16
3 7 23
9 7 21
9 14 19
3 1 20
3 1 5
12 14 19
3 14 2
12 1 46
3 14 5
9 14 44
6 14 26
9 14 16
9 14 34
6 7 42
3 14 27
1 7 9
1 7 41
15 14 19
12 7 13
3 7 10
1 7 2
17