#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