全体站点的往返距离

难度：T2

【知识点：Dijkstra最短路】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

给出有向带权图和站点 $s$。对每个顶点，分别考虑从 $s$ 到该点、再返回 $s$ 的最短往返距离，求这些往返距离的总和。不是用一次旅行走遍全部顶点。

输入格式

其中 $n$ 为顶点数，顶点编号为 $1$ 到 $n$；$m$ 为随后给出的带权边条数。每条带权边独占一行，依次为 $u,v,w$，表示从 $u$ 到 $v$ 的边及权值 $w$；无向边可双向通行，有向边只能从 $u$ 到 $v$ 通行。

输入$n$、$m$、$s$及$m$条有向非负权边$u$、$v$、$w$。每个站点分别从$s$往返，不是一趟走遍所有站点。

输出格式

任意站点不能往返则输出-$1$；否则输出所有站点往返最短距离之和。

数据范围

$1\le n\le 500$，$0\le m\le 200000$，$0\le w\le 10^9$，编号在$1$..$n$。

样例输入

1 0 1

样例输出

0

样例输入 2

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

样例输出 2

11

样例说明 2

两个非源点的最短往返距离分别为 $5,6$，总和为 $11$。