#include <climits>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
void print( std::vector<int> & a )
{
for (auto i : a)
std::cout << i << " ";
std::cout << std::endl;
}
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);
print(distances);
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);
print(result);
}
return 0;
}
I2luY2x1ZGUgPGNsaW1pdHM+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHF1ZXVlPgoKdm9pZCBwcmludCggc3RkOjp2ZWN0b3I8aW50PiAmIGEgKQp7CiAgICBmb3IgKGF1dG8gaSA6IGEpCiAgICAgICAgc3RkOjpjb3V0IDw8IGkgPDwgIiAiOwogICAgc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKfQoKY2xhc3MgR3JhcGgKewpwcml2YXRlOgogICAgc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8c3RkOjpwYWlyPGludCwgaW50Pj4+IGFkajsKICAgIHN0ZDo6dmVjdG9yPGludD4gZGlzdGFuY2VzOwogICAgc3RkOjp2ZWN0b3I8aW50PiBwYXRoOwogICAgY29uc3QgaW50IElORiA9IElOVF9NQVg7CiAgICBpbnQgdmVydGV4ZXNfY291bnQgPSAwLCBlZGdlc19jb3VudCA9IDA7CiAgICB2b2lkIHJlbGF4IChpbnQgc3RhcnQsIGludCBlbmQsIGludCBsZW5ndGgpOwpwdWJsaWM6CiAgICB0eXBlZGVmIHN0ZDo6dmVjdG9yPGludD4gcmVzdWx0OwogICAgR3JhcGgoKTsKICAgIEdyYXBoKGludCB2ZXJ0ZXhlcywgaW50IGVkZ2VzKTsKICAgIH5HcmFwaCgpOwogICAgdm9pZCBpbnB1dCgpOwogICAgdm9pZCBvdXRwdXQoKTsKICAgIHJlc3VsdCBkaWprc3RyYShpbnQgc3RhcnQpOwp9OwoKR3JhcGg6OkdyYXBoKCkge30KCkdyYXBoOjp+R3JhcGgoKSB7fQoKR3JhcGg6OkdyYXBoKGludCB2ZXJ0ZXhlcywgaW50IGVkZ2VzKQp7CiAgICB2ZXJ0ZXhlc19jb3VudCA9IHZlcnRleGVzOwogICAgZWRnZXNfY291bnQgICAgPSBlZGdlczsKICAgIGFkai5yZXNpemUodmVydGV4ZXMgKyAxKTsKICAgIGRpc3RhbmNlcy5yZXNpemUodmVydGV4ZXMgKyAxLCBJTkYpOwogICAgcGF0aC5yZXNpemUodmVydGV4ZXMgKyAxLCAtMSk7Cn0KCnZvaWQgR3JhcGg6OmlucHV0KCkKewogICAgaW50IHN0YXJ0ID0gMCwgZW5kID0gMCwgbGVuZ3RoID0gMDsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgZWRnZXNfY291bnQ7ICsraSkKICAgIHsKICAgICAgICBzdGQ6OmNpbiA+PiBzdGFydCA+PiBlbmQgPj4gbGVuZ3RoOwogICAgICAgIGFkaltzdGFydF0ucHVzaF9iYWNrIChzdGQ6Om1ha2VfcGFpcihsZW5ndGgsIGVuZCkpOwogICAgICAgIGFkaltlbmRdLnB1c2hfYmFjayAoc3RkOjptYWtlX3BhaXIobGVuZ3RoLCBzdGFydCkpOwogICAgfQp9CgpHcmFwaDo6cmVzdWx0CkdyYXBoOjpkaWprc3RyYSAoaW50IHN0YXJ0KQp7CiAgICBkaXN0YW5jZXNbc3RhcnRdID0gMDsKICAgIHBhdGhbc3RhcnRdID0gc3RhcnQ7CiAgICBzdGQ6OnByaW9yaXR5X3F1ZXVlPHN0ZDo6cGFpcjxpbnQsIGludD4sCiAgICAgICAgICAgICAgICAgICAgICAgIHN0ZDo6dmVjdG9yPHN0ZDo6cGFpcjxpbnQsIGludD4+LAogICAgICAgICAgICAgICAgICAgICAgICBzdGQ6OmdyZWF0ZXI8c3RkOjpwYWlyPGludCwgaW50Pj4+IHE7CiAgICBxLnB1c2goc3RkOjptYWtlX3BhaXIoMCwgc3RhcnQpKTsKICAgIHdoaWxlICghcS5lbXB0eSgpKQogICAgewogICAgICAgIGludCBjdXJyZW50ID0gcS50b3AoKS5zZWNvbmQ7CiAgICAgICAgaW50IGxlbiAgICAgPSBxLnRvcCgpLmZpcnN0OwogICAgICAgIHEucG9wKCk7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBhZGpbY3VycmVudF0uc2l6ZSgpOyArK2kpCiAgICAgICAgewogICAgICAgICAgICBpbnQgdG8gICAgID0gYWRqW2N1cnJlbnRdW2ldLnNlY29uZDsKICAgICAgICAgICAgaW50IGxlbmd0aCA9IGFkaltjdXJyZW50XVtpXS5maXJzdDsKICAgICAgICAgICAgLy8gUmVsYXhhdGlvbnMKICAgICAgICAgICAgaWYgKGRpc3RhbmNlc1t0b10gPiBkaXN0YW5jZXNbY3VycmVudF0gKyBsZW5ndGgpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHBhdGhbdG9dID0gY3VycmVudDsgICAgIAogICAgICAgICAgICAgICAgZGlzdGFuY2VzW3RvXSA9IGRpc3RhbmNlc1tjdXJyZW50XSArIGxlbmd0aDsKICAgICAgICAgICAgICAgIHEucHVzaChzdGQ6Om1ha2VfcGFpcihkaXN0YW5jZXNbdG9dLCB0bykpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgLy8gUmVwbGFjZSBJTkYgYnkgLTEKICAgIC8vc3RkOjpyZXBsYWNlIChkaXN0YW5jZXMuYmVnaW4oKSwgZGlzdGFuY2VzLmVuZCgpLCBJTkYsIC0xKTsKICAgIHByaW50KGRpc3RhbmNlcyk7CiAgICByZXR1cm4gZGlzdGFuY2VzOwp9CgoKaW50IG1haW4oKSB7CiAgICBpbnQgbnRlc3RzID0gMCwgbm9kZXMgPSAwLCBlZGdlcyA9IDAsIHN0YXJ0ID0gMDsKICAgIHN0ZDo6Y2luID4+IG50ZXN0czsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbnRlc3RzOyArK2kpCiAgICB7CiAgICAgICAgc3RkOjpjaW4gPj4gbm9kZXMgPj4gZWRnZXM7CiAgICAgICAgR3JhcGggZyhub2RlcywgZWRnZXMpOwogICAgICAgIGcuaW5wdXQoKTsKICAgICAgICBzdGQ6OmNpbiA+PiBzdGFydDsKICAgICAgICBhdXRvIHJlc3VsdCA9IGcuZGlqa3N0cmEgKHN0YXJ0KTsKICAgICAgICBwcmludChyZXN1bHQpOwogICAgfQogICAgcmV0dXJuIDA7Cn0=