Job at Todechef Problem Code: ISITSP

 

Preface:

There is no need for introduction of uses of shortest path algorithms in real life. Used intensively in industrial applications like GPS, finding shortest path has been of interest to many researchers.

However, the most important, yet undervalued aspect for shortest path algorithm is the graph itself. Often, due to some special properties of the graph needed in our application, we can make certain assumptions −$-$ which would otherwise be wrong in general. This opens up a new world of optimizing the graph algorithms because certain invalid algorithms might also produce correct results because of the earlier assumptions…

Statement:

In a far away Galaxy of Tilky Way, there was a planet Tarth where the sport of Tompetitive Toding was very popular. According to legends, there lived a setter who gave out interview questions asked at Todechef and Tirecti.

Tima and Tuchika were giving their interview for the role of developers at Todechef. Their interviewers, Ms Teha, Ms Tamesh and Ms Takkoth were die hard fans of selfies, food and graph algorithms. Hence, they asked Tima and Tuchika to find the shortest path in the given un-directed graph. They said that this graph has a very special property - The edges will have weight of EITHER k1$k_1$ OR k2$k_2$.

Tima, who was too busy dating, to study properly for interview, said that she would apply 0−1$0-1$ BFS$BFS$ on it by taking the minimum weight to correspond to weight 0$0$ and maximum weight to correspond to weight 1$1$ in the algorithm. Tuchika, who studied very very hard to impress her crush, said that she'd apply Bellman$Bellman$ Ford$Ford$ algorithm to it and report the answer directly.

Ms Teha, Ms Tamesh and Ms Takkoth were not happy. They expected better answers for this job with salary of 1018${10}^{18}$ Todechef Kaddus per month. Hence, now its upto you to make both Tima and Tuchika realize their mistake!!

You need to report 3$3$ things - the correct answer, and the absolute differences between correct answer and answers given by Tima and Tuchika respectively. You need to report this assuming starting node to be St$S_t$ and taking every node as target node one by one.

(Note- If multiple edges lead to some node V$V$, then Tima will visit all the edges, and see which one gives minimum distance. This is the core step of 0−1$0-1$ BFS$BFS$)

Input:

• The first line contains 3$3$ integers - N$N$ M$M$ St$S_t$ , i.e. number of nodes, number of edges and starting node respectively.
• Next M$M$ lines contain 3$3$ integers u$u$ v$v$ and W$W$ denoting that there is an edge between node u$u$ and node v$v$ of weight W$W$

Output:

Output N$N$ lines −$-$ where i′th$i^{\prime }th$ line denotes answer if node i$i$ was the target node. Each line should be containing 3$3$ integers- Ac$A_c$ D1$D_1$ and D2$D_2$ - where Ac$A_c$ is the correct answer for shortest path, D1$D_1$ is absolute difference between correct answer and Tima's answer, and D2$D_2$ is similarly absolute difference between Tuchika's and correct answer.

Constraints

• 1≤N≤105$1\le N\le {10}^5$
• 1≤M≤1.5∗105$1\le M\le 1.5\ast {10}^5$
• 1≤St,u,v≤N$1\le S_t,u,v\le N$
• 0≤W≤109$0\le W\le {10}^9$
• W$W$ will have at most 2$2$ distinct values in the graph. It is very much possible that k1=k2$k_1=k_2$, making the graph have only 1$1$ distinct value.

Note- Input can be huge. Prefer fast IO methods.

Subtasks:

• 5% points - Given graph is a tree.
• 8% points - N≤100$N\le 100$
• 8% points - One of the weights is 0$0$
• 9% points - N≤5000$N\le 5000$
• 70% points - Original Constraints

Sample Input:

2 1 1
1 2 5

Sample Output:

0 0 0
5 0 0

EXPLANATION:

We see that it is a simple graph with node 1$1$ connected to node 2$2$ by a simple edge of weight 5$5$. We can verify that the shortest path from node 1$1$ to node 2$2$ must use this edge, and hence be of weight 5$5$. Also, for this particular graph, both algorithms give correct answer.

(Note- Distance of a node to itself is always 0$0$).

NOTES:

The 0−1$0-1$ BFS$BFS$ algorithm can be

for all v in vertices:
    dist[v] = inf
dist[source] = 0;
deque d
d.push_front(source)
while d.empty() == false:
    vertex = get front element and pop as in BFS.
    for all edges e of form (vertex , u):
        if travelling e shortens distance to u:
            update(dist[u]);
            if e.weight = 1:
                d.push_back(u)
            else:
                d.push_front(u)