Sum of Shortest Paths

You are given a weighted and undirected graph representing a network of cities connected by roads. There are n cities and m roads. Each road connects two different cities and has an associated non-negative weight representing its length.

Your task is to compute the sum of the shortest path distances from a given starting city to all other cities. For any city that is unreachable from the starting city, consider its distance as -1.

Formally, let \(d_i\) be defined as follows for each city \(i\):

[ d_i = \begin{cases} 0, & \text{if } i \text{ is the starting city},\ \text{the shortest distance from the starting city to } i, & \text{if } i \text{ is reachable},\ -1, & \text{if } i \text{ is unreachable}. \end{cases} ]

You need to calculate the sum:

[ S = \sum_{i=1}^{n} d_i ]

It is recommended to use Dijkstra's algorithm for an efficient solution.

inputFormat

The input is given from stdin and has the following format:

n m
u1 v1 w1
u2 v2 w2
... (m lines total)
start

Where:

• n is the number of cities (nodes).
• m is the number of roads (edges).
• Each of the next m lines contains three integers u, v, and w denoting a road between cities u and v with length w.
• start is the starting city from which distances are calculated.

outputFormat

The output is a single integer printed to stdout representing the sum of the shortest distances from the starting city to every city. For cities that cannot be reached, include -1 in the sum.

## sample

4 4
1 2 4
1 3 2
2 3 1
3 4 5
1

12