股票经纪人要在一群人(n 个人的编号为0~n-1)中散布一个传言,传言只在认识的人中间传递。题目中给出了人与人的认识关系以及传言在某两个认识的人中传递所需要的时间。编写程序求出以哪个人为起点可以在耗时最短的情况下让所有人收到消息。

这是一个经典的图论问题，可以用 Dijkstra 算法或者 Floyd 算法来解决。下面分别介绍这两种算法的实现方法。

## Dijkstra 算法

Dijkstra 算法是一种单源最短路径算法，用于求解一个节点到其他所有节点的最短路径。在本问题中，我们需要以每个人为起点分别运行 Dijkstra 算法，然后取所有起点中的最小值。

具体实现时，我们可以使用一个数组 $dist$ 来记录从起点到各个节点的最短距离，一个数组 $vis$ 来记录每个节点是否已经被访问过，以及一个邻接矩阵 $graph$ 来表示人与人之间的认识关系和传言传递所需的时间。

算法步骤如下：

1. 初始化 $dist$ 数组为无穷大，除起点 $s$ 外，将 $vis[s]$ 设为 1，$dist[s]$ 设为 0。
2. 从未访问过的节点中选择一个距离起点最近的节点 $u$，将 $vis[u]$ 设为 1。
3. 对于节点 $u$ 的每个邻居节点 $v$，如果 $v$ 未被访问过且从 $s$ 到 $u$ 再到 $v$ 的距离比当前记录的 $dist[v]$ 更短，则更新 $dist[v]$ 的值。
4. 重复步骤 2 和步骤 3，直到所有节点都被访问过或不存在未访问过的节点。

最后，取所有起点中的最小值作为答案即可。

以下是 Python 代码实现：

import sys

# 读入数据
n, m = map(int, input().split())
graph = [[sys.maxsize] * n for _ in range(n)]
for i in range(m):
    u, v, w = map(int, input().split())
    graph[u][v] = graph[v][u] = w

# 运行 Dijkstra 算法
def dijkstra(s):
    dist = [sys.maxsize] * n
    vis = [0] * n
    dist[s] = 0
    vis[s] = 1
    for i in range(n - 1):
        min_dist = sys.maxsize
        min_node = -1
        for j in range(n):
            if not vis[j] and dist[j] < min_dist:
                min_dist = dist[j]
                min_node = j
        vis[min_node] = 1
        for j in range(n):
            if not vis[j] and dist[min_node] + graph[min_node][j] < dist[j]:
                dist[j] = dist[min_node] + graph[min_node][j]
    return dist

ans = sys.maxsize
for i in range(n):
    ans = min(ans, max(dijkstra(i)))
print(ans)

## Floyd 算法

Floyd 算法是一种多源最短路径算法，用于求解任意两个节点之间的最短路径。在本问题中，我们可以用 Floyd 算法来求解任意两个人之间的最短时间，然后以每个人为起点分别遍历所有节点，求出耗时最短的情况。

具体实现时，我们可以使用一个邻接矩阵 $graph$ 来表示人与人之间的认识关系和传言传递所需的时间。算法步骤如下：

1. 初始化邻接矩阵 $graph$，将没有认识关系的两个人之间的距离设为无穷大。
2. 对于任意两个节点 $i$ 和 $j$，如果存在一个节点 $k$ 使得从 $i$ 到 $k$ 再到 $j$ 的距离比当前记录的 $graph[i][j]$ 更短，则更新 $graph[i][j]$ 的值。
3. 以每个人为起点分别遍历所有节点，求出耗时最短的情况。

以下是 Python 代码实现：

import sys

# 读入数据
n, m = map(int, input().split())
graph = [[sys.maxsize] * n for _ in range(n)]
for i in range(m):
    u, v, w = map(int, input().split())
    graph[u][v] = graph[v][u] = w

# 运行 Floyd 算法
for k in range(n):
    for i in range(n):
        for j in range(n):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

# 以每个人为起点分别遍历所有节点，求出耗时最短的情况
ans = sys.maxsize
for i in range(n):
    max_dist = 0
    for j in range(n):
        if i != j:
            max_dist = max(max_dist, graph[i][j])
    ans = min(ans, max_dist)
print(ans)