#include <climits>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#define __DEBUG
#ifdef __DEBUG
#define print_pair(p) do{std::cout << "(" << ((p).first) << ", "\
<< ((p).second) << ")" << std::endl;}while(0);
#endif
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);
distances.resize(vertexes, INF);
path.resize(vertexes, -1);
}
void Graph::input()
{
#ifdef __DEBUG
std::cout << "default distances:" << std::endl;
for (auto &i : distances)
std::cout << i << " ";
std::cout << std::endl;
#endif
int start = 0, end = 0, length = 0;
for (int i = 0; i < edges_count; ++i)
{
std::cin >> start >> end >> length;
adj[start - 1].push_back (std::make_pair(length, end - 1));
}
#ifdef __DEBUG
std::cout << "adjacency lists:" << std::endl;
for (int i = 0; i < adj.size(); ++i)
{
for (int j = 0; j < adj[i].size(); ++j)
{
std::cout << "(" << i << ", " << (adj[i][j].second) << ")" << std::endl;
}
std::cout << std::endl;
}
#endif
}
Graph::result
Graph::dijkstra (int start)
{
#ifdef __DEBUG
std::cout << "Dijkstra algorithm tracing:" << std::endl;
#endif
distances[start - 1] = 0;
std::set<std::pair<int, int>> q;
q.insert (std::make_pair(distances[start - 1], start - 1));
while (!q.empty())
{
#ifdef __DEBUG
std::cout << "top element of a set: ";
print_pair(*q.begin());
#endif
int current = q.begin()->second;
q.erase(q.begin());
#ifdef __DEBUG
std::cout << "current vertex: " << current << std::endl;
#endif
for (int i = 0; i < adj[current].size(); ++i)
{
#ifdef __DEBUG
std::cout << "current vertex: " << current;
std::cout << " and current state of distances array is: " << std::endl;
for (auto i: distances)
std::cout << i << " ";
std::cout << std::endl;
#endif
int to = adj[current][i].second;
int length = adj[current][i].first;
// Relaxations
if (distances[to] > distances[current] + length)
{
#ifdef __DEBUG
std::cout << "relaxation for edge (" << current << ", " << to << ") ";
std::cout << "with weight " << length << std::endl;
#endif
q.erase(std::make_pair(distances[to], to));
distances[to] = distances[current] + length;
path[to] = current;
q.insert(std::make_pair(distances[to], to));
}
}
}
// Replace INF by -1
std::replace (distances.begin(), distances.end(), INF, -1);
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;
}