#include <climits>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
class Graph
{
private:
struct node
{
int vertex, length;
bool operator < (const node &x) const
{
return length > x.length;
}
};
std::vector<std::vector<std::pair<int, int>>> graph;
std::vector<int> distance;
const int INF = INT_MAX;
int vertexes_count = 0, edges_count = 0;
public:
typedef std::vector<int> result;
Graph();
Graph(int vertexes, int edges);
~Graph();
void input();
result dijkstra(int start);
};
Graph::Graph() {}
Graph::~Graph() {}
Graph::Graph(int vertexes, int edges)
{
vertexes_count = vertexes;
edges_count = edges;
graph.resize(vertexes + 1);
distance.resize(vertexes + 1, INF);
}
void Graph::input()
{
int start = 0, end = 0, length = 0;
for (int i = 0; i < edges_count; ++i)
{
std::cin >> start >> end >> length;
graph[start].push_back (std::make_pair(end, length));
graph[end].push_back (std::make_pair(start, length));
}
}
Graph::result
Graph::dijkstra (int start)
{
distance[start] = 0;
std::priority_queue<node> q;
q.push({start, 0});
while (!q.empty())
{
int current = q.top().vertex;
q.pop();
for (auto &adjacent : graph[current])
{
int to = adjacent.first;
int length = adjacent.second;
// Relaxations
if (distance[to] > distance[current] + length)
{
distance[to] = distance[current] + length;
q.push({to, distance[to]});
}
}
}
// Replace INF by -1
std::replace (distance.begin(), distance.end(), INF, -1);
return distance;
}
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 = 1; j < result.size(); ++j)
{
if (j != start)
std::cout << result[j] << " ";
}
std::cout << std::endl;
}
return 0;
}
I2luY2x1ZGUgPGNsaW1pdHM+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHF1ZXVlPgoKY2xhc3MgR3JhcGgKewpwcml2YXRlOgogICAgc3RydWN0IG5vZGUKICAgIHsKICAgICAgICBpbnQgdmVydGV4LCBsZW5ndGg7CiAgICAgICAgYm9vbCBvcGVyYXRvciA8IChjb25zdCBub2RlICZ4KSBjb25zdAogICAgICAgIHsKICAgICAgICAgICAgcmV0dXJuIGxlbmd0aCA+IHgubGVuZ3RoOwogICAgICAgIH0KICAgIH07CiAgICAKICAgIHN0ZDo6dmVjdG9yPHN0ZDo6dmVjdG9yPHN0ZDo6cGFpcjxpbnQsIGludD4+PiBncmFwaDsKICAgIHN0ZDo6dmVjdG9yPGludD4gZGlzdGFuY2U7CiAgICAKICAgIGNvbnN0IGludCBJTkYgPSBJTlRfTUFYOwogICAgaW50IHZlcnRleGVzX2NvdW50ID0gMCwgZWRnZXNfY291bnQgPSAwOwpwdWJsaWM6CiAgICB0eXBlZGVmIHN0ZDo6dmVjdG9yPGludD4gcmVzdWx0OwogICAgR3JhcGgoKTsKICAgIEdyYXBoKGludCB2ZXJ0ZXhlcywgaW50IGVkZ2VzKTsKICAgIH5HcmFwaCgpOwogICAgdm9pZCBpbnB1dCgpOwogICAgcmVzdWx0IGRpamtzdHJhKGludCBzdGFydCk7Cn07CgpHcmFwaDo6R3JhcGgoKSB7fQoKR3JhcGg6On5HcmFwaCgpIHt9CgpHcmFwaDo6R3JhcGgoaW50IHZlcnRleGVzLCBpbnQgZWRnZXMpCnsKICAgIHZlcnRleGVzX2NvdW50ID0gdmVydGV4ZXM7CiAgICBlZGdlc19jb3VudCAgICA9IGVkZ2VzOwogICAgZ3JhcGgucmVzaXplKHZlcnRleGVzICsgMSk7CiAgICBkaXN0YW5jZS5yZXNpemUodmVydGV4ZXMgKyAxLCBJTkYpOwp9Cgp2b2lkIEdyYXBoOjppbnB1dCgpCnsKICAgIGludCBzdGFydCA9IDAsIGVuZCA9IDAsIGxlbmd0aCA9IDA7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IGVkZ2VzX2NvdW50OyArK2kpCiAgICB7CiAgICAgICAgc3RkOjpjaW4gPj4gc3RhcnQgPj4gZW5kID4+IGxlbmd0aDsKICAgICAgICBncmFwaFtzdGFydF0ucHVzaF9iYWNrIChzdGQ6Om1ha2VfcGFpcihlbmQsIGxlbmd0aCkpOwogICAgICAgIGdyYXBoW2VuZF0ucHVzaF9iYWNrIChzdGQ6Om1ha2VfcGFpcihzdGFydCwgbGVuZ3RoKSk7CiAgICB9Cn0KCkdyYXBoOjpyZXN1bHQKR3JhcGg6OmRpamtzdHJhIChpbnQgc3RhcnQpCnsKICAgIGRpc3RhbmNlW3N0YXJ0XSA9IDA7CiAgICAKICAgIHN0ZDo6cHJpb3JpdHlfcXVldWU8bm9kZT4gcTsKICAgIAogICAgcS5wdXNoKHtzdGFydCwgMH0pOwogICAgCiAgICB3aGlsZSAoIXEuZW1wdHkoKSkKICAgIHsKICAgICAgICBpbnQgY3VycmVudCA9IHEudG9wKCkudmVydGV4OwogICAgICAgIHEucG9wKCk7CiAgICAgICAgCiAgICAgICAgZm9yIChhdXRvICZhZGphY2VudCA6IGdyYXBoW2N1cnJlbnRdKQogICAgICAgIHsKICAgICAgICAgICAgaW50IHRvICAgICA9IGFkamFjZW50LmZpcnN0OwogICAgICAgICAgICBpbnQgbGVuZ3RoID0gYWRqYWNlbnQuc2Vjb25kOwogICAgICAgICAgICAvLyBSZWxheGF0aW9ucwogICAgICAgICAgICBpZiAoZGlzdGFuY2VbdG9dID4gZGlzdGFuY2VbY3VycmVudF0gKyBsZW5ndGgpCiAgICAgICAgICAgIHsgICAgCiAgICAgICAgICAgICAgICBkaXN0YW5jZVt0b10gPSBkaXN0YW5jZVtjdXJyZW50XSArIGxlbmd0aDsKICAgICAgICAgICAgICAgIHEucHVzaCh7dG8sIGRpc3RhbmNlW3RvXX0pOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgLy8gUmVwbGFjZSBJTkYgYnkgLTEKICAgIHN0ZDo6cmVwbGFjZSAoZGlzdGFuY2UuYmVnaW4oKSwgZGlzdGFuY2UuZW5kKCksIElORiwgLTEpOwogICAgcmV0dXJuIGRpc3RhbmNlOwp9CgppbnQgbWFpbigpIHsKICAgIGludCBudGVzdHMgPSAwLCBub2RlcyA9IDAsIGVkZ2VzID0gMCwgc3RhcnQgPSAwOwogICAgc3RkOjpjaW4gPj4gbnRlc3RzOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBudGVzdHM7ICsraSkKICAgIHsKICAgICAgICBzdGQ6OmNpbiA+PiBub2RlcyA+PiBlZGdlczsKICAgICAgICBHcmFwaCBnKG5vZGVzLCBlZGdlcyk7CiAgICAgICAgZy5pbnB1dCgpOwogICAgICAgIHN0ZDo6Y2luID4+IHN0YXJ0OwogICAgICAgIGF1dG8gcmVzdWx0ID0gZy5kaWprc3RyYSAoc3RhcnQpOwogICAgICAgIGZvciAoaW50IGogPSAxOyBqIDwgcmVzdWx0LnNpemUoKTsgKytqKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKGogIT0gc3RhcnQpCiAgICAgICAgICAgICAgICBzdGQ6OmNvdXQgPDwgcmVzdWx0W2pdIDw8ICIgIjsKICAgICAgICB9CiAgICAgICAgc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKICAgIH0KICAgIHJldHVybiAwOwp9