#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)
{
std::cout << "inner for" << std::endl;
path[to] = current;
distances[to] = distances[current] + length;
q.push(std::make_pair(distances[to], to));
for (auto i : distances)
std::cout << i << " ";
std::cout << std::endl;
}
}
}
// 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;
}
I2luY2x1ZGUgPGNsaW1pdHM+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHF1ZXVlPgoKY2xhc3MgR3JhcGgKewpwcml2YXRlOgogICAgc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8c3RkOjpwYWlyPGludCwgaW50Pj4+IGFkajsKICAgIHN0ZDo6dmVjdG9yPGludD4gZGlzdGFuY2VzOwogICAgc3RkOjp2ZWN0b3I8aW50PiBwYXRoOwogICAgY29uc3QgaW50IElORiA9IElOVF9NQVg7CiAgICBpbnQgdmVydGV4ZXNfY291bnQgPSAwLCBlZGdlc19jb3VudCA9IDA7CiAgICB2b2lkIHJlbGF4IChpbnQgc3RhcnQsIGludCBlbmQsIGludCBsZW5ndGgpOwpwdWJsaWM6CiAgICB0eXBlZGVmIHN0ZDo6dmVjdG9yPGludD4gcmVzdWx0OwogICAgR3JhcGgoKTsKICAgIEdyYXBoKGludCB2ZXJ0ZXhlcywgaW50IGVkZ2VzKTsKICAgIH5HcmFwaCgpOwogICAgdm9pZCBpbnB1dCgpOwogICAgdm9pZCBvdXRwdXQoKTsKICAgIHJlc3VsdCBkaWprc3RyYShpbnQgc3RhcnQpOwp9OwoKR3JhcGg6OkdyYXBoKCkge30KCkdyYXBoOjp+R3JhcGgoKSB7fQoKR3JhcGg6OkdyYXBoKGludCB2ZXJ0ZXhlcywgaW50IGVkZ2VzKQp7CiAgICB2ZXJ0ZXhlc19jb3VudCA9IHZlcnRleGVzOwogICAgZWRnZXNfY291bnQgICAgPSBlZGdlczsKICAgIGFkai5yZXNpemUodmVydGV4ZXMgKyAxKTsKICAgIGRpc3RhbmNlcy5yZXNpemUodmVydGV4ZXMgKyAxLCBJTkYpOwogICAgcGF0aC5yZXNpemUodmVydGV4ZXMgKyAxLCAtMSk7Cn0KCnZvaWQgR3JhcGg6OmlucHV0KCkKewogICAgaW50IHN0YXJ0ID0gMCwgZW5kID0gMCwgbGVuZ3RoID0gMDsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgZWRnZXNfY291bnQ7ICsraSkKICAgIHsKICAgICAgICBzdGQ6OmNpbiA+PiBzdGFydCA+PiBlbmQgPj4gbGVuZ3RoOwogICAgICAgIGFkaltzdGFydF0ucHVzaF9iYWNrIChzdGQ6Om1ha2VfcGFpcihsZW5ndGgsIGVuZCkpOwogICAgICAgIGFkaltlbmRdLnB1c2hfYmFjayAoc3RkOjptYWtlX3BhaXIobGVuZ3RoLCBzdGFydCkpOwogICAgfQp9CgpHcmFwaDo6cmVzdWx0CkdyYXBoOjpkaWprc3RyYSAoaW50IHN0YXJ0KQp7CiAgICBkaXN0YW5jZXNbc3RhcnRdID0gMDsKICAgIHBhdGhbc3RhcnRdID0gc3RhcnQ7CiAgICBzdGQ6OnByaW9yaXR5X3F1ZXVlPHN0ZDo6cGFpcjxpbnQsIGludD4sCiAgICAgICAgICAgICAgICAgICAgICAgIHN0ZDo6dmVjdG9yPHN0ZDo6cGFpcjxpbnQsIGludD4+LAogICAgICAgICAgICAgICAgICAgICAgICBzdGQ6OmdyZWF0ZXI8c3RkOjpwYWlyPGludCwgaW50Pj4+IHE7CiAgICBxLnB1c2goc3RkOjptYWtlX3BhaXIoMCwgc3RhcnQpKTsKICAgIHdoaWxlICghcS5lbXB0eSgpKQogICAgewogICAgICAgIGludCBjdXJyZW50ID0gcS50b3AoKS5zZWNvbmQ7CiAgICAgICAgaW50IGxlbiAgICAgPSBxLnRvcCgpLmZpcnN0OwogICAgICAgIHEucG9wKCk7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBhZGpbY3VycmVudF0uc2l6ZSgpOyArK2kpCiAgICAgICAgewogICAgICAgICAgICBpbnQgdG8gICAgID0gYWRqW2N1cnJlbnRdW2ldLnNlY29uZDsKICAgICAgICAgICAgaW50IGxlbmd0aCA9IGFkaltjdXJyZW50XVtpXS5maXJzdDsKICAgICAgICAgICAgLy8gUmVsYXhhdGlvbnMKICAgICAgICAgICAgaWYgKGRpc3RhbmNlc1t0b10gPiBkaXN0YW5jZXNbY3VycmVudF0gKyBsZW5ndGgpCiAgICAgICAgICAgIHsgICAKICAgICAgICAgICAgICAgIHN0ZDo6Y291dCA8PCAiaW5uZXIgZm9yIiA8PCBzdGQ6OmVuZGw7CiAgICAgICAgICAgICAgICBwYXRoW3RvXSA9IGN1cnJlbnQ7ICAgICAKICAgICAgICAgICAgICAgIGRpc3RhbmNlc1t0b10gPSBkaXN0YW5jZXNbY3VycmVudF0gKyBsZW5ndGg7CiAgICAgICAgICAgICAgICBxLnB1c2goc3RkOjptYWtlX3BhaXIoZGlzdGFuY2VzW3RvXSwgdG8pKTsKICAgICAgICAgICAgICAgIGZvciAoYXV0byBpIDogZGlzdGFuY2VzKQogICAgICAgICAgICAgICAgICAgIHN0ZDo6Y291dCA8PCBpIDw8ICIgIjsKICAgICAgICAgICAgICAgIHN0ZDo6Y291dCA8PCBzdGQ6OmVuZGw7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICAvLyBSZXBsYWNlIElORiBieSAtMQogICAgc3RkOjpyZXBsYWNlIChkaXN0YW5jZXMuYmVnaW4oKSwgZGlzdGFuY2VzLmVuZCgpLCBJTkYsIC0xKTsKICAgIGZvciAoYXV0byBpIDogZGlzdGFuY2VzKQogICAgICAgIHN0ZDo6Y291dCA8PCBpIDw8ICIgIjsKICAgIHN0ZDo6Y291dCA8PCBzdGQ6OmVuZGw7CiAgICByZXR1cm4gZGlzdGFuY2VzOwp9CgppbnQgbWFpbigpIHsKICAgIGludCBudGVzdHMgPSAwLCBub2RlcyA9IDAsIGVkZ2VzID0gMCwgc3RhcnQgPSAwOwogICAgc3RkOjpjaW4gPj4gbnRlc3RzOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBudGVzdHM7ICsraSkKICAgIHsKICAgICAgICBzdGQ6OmNpbiA+PiBub2RlcyA+PiBlZGdlczsKICAgICAgICBHcmFwaCBnKG5vZGVzLCBlZGdlcyk7CiAgICAgICAgZy5pbnB1dCgpOwogICAgICAgIHN0ZDo6Y2luID4+IHN0YXJ0OwogICAgICAgIGF1dG8gcmVzdWx0ID0gZy5kaWprc3RyYSAoc3RhcnQpOwogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgcmVzdWx0LnNpemUoKTsgKytqKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKGogIT0gc3RhcnQpCiAgICAgICAgICAgICAgICBzdGQ6OmNvdXQgPDwgcmVzdWx0W2ldIDw8ICIgIjsKICAgICAgICB9CiAgICAgICAgc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKICAgIH0KICAgIHJldHVybiAwOwp9