思路

倍增优化的动态规划。用 $f(k, i, j)$ 表示从 $i$ 到 $j$ 恰好经过 $k$ 条边的最短距离。我们可能会认为需要枚举 $k$ 如何构成，即 $1 + (k - 1), 2 + (k - 2), \cdots$。但换个角度想，对于 $i, j$ 之间经过 $k$ 条边的任意一条最短路径，它上面的第 $x + 1 \in [1, k + 1]$ 个点，记为 $v_{x + 1}$，必然满足：

$$ f(k, i, j) = f(x, i, v_{x + 1}) + f(k - x, v_{x + 1}, j) $$

当 $x + 1$ 取 $2$ 时，有

$$ f(k, i, j) = f(1, i, v_{2}) + f(k - 1, v_{2}, j) $$

只要把所有点枚举一遍，必然能枚举到每条路径的第 $2$ 个点：

for k in range(1, n + 1):
  for i in range(1, n + 1):
    for j in range(1, n + 1):
      for v in range(1, n + 1):
        f[k][i][j] = min(f[k][i][j], f[1][i][v] + f[k - 1][v][j])

再想一想，既然上文的 $x + 1$ 可以任意取，那不妨在 $k$ 为偶数时取 $k / 2$，于是有以下分治做法：

def f(k, i, j)
  if k == 0:
    if i == j: return 0
    return INF
  if k == 1: return g[i][j]

  x = 1 if k & 1 else k // 2
  res = INF
  for v in range(1, n + 1):
    res = min(res, f(x, i, v) + f(k - x, v, j))
  return INF

但以上两种做法复杂度都太高，既然最短距离可以任意取中间点相加，而前后又可以单独算，且这个过程可以递归，说明它具有结合律，即可以先算路径的任意一部分，因此可用倍增法优化，时间复杂度 $O(T^3logN)$。

N, INF = 210, 0x3f3f3f3f
rl = lambda: map(int, input().split())
tpl = lambda: [[INF] * N for _ in range(N)]

n, m, S, E = rl()
idx = dict()
g = tpl()

def get_id(x):
  if x not in idx:
    idx[x] = len(idx) + 1
  return idx[x]

def add(a, b):
  """
    a: 经过 x 条边的最短距离
    b: 经过 y 条边的最短距离
  res: 经过 x + y 条边的最短距离
  """
  n = len(idx)
  res = tpl()
  for k in range(1, n + 1):
    for i in range(1, n + 1):
      for j in range(1, n + 1):
        res[i][j] = min(res[i][j], a[i][k] + b[k][j])
  return res

def qadd():
  """
    g: 经过 1, 2, 4, 8, ..., 条边的最短距离
  res: 初始化为经过零条边的最短距离，之后根
       据 n 的二进制位加上相应 g，最终为经
       过 n 条边的最短距离
  """
  res = tpl()
  for i in range(len(idx)): res[i][i] = 0

  global n, g
  while n:
    if n & 1: res = add(res, g)
    g = add(g, g)
    n >>= 1

  return res[S][E]

def solve():
  global S, E
  S, E = get_id(S), get_id(E)
  for _ in range(m):
    c, a, b = rl()
    a, b = get_id(a), get_id(b)
    g[a][b] = g[b][a]= min(g[a][b], c)

  print(qadd())

solve()

补充

$Floyd$ 算法的状态表示为：用 $f(k, i, j)$ 表示从 $i$ 到 $j$，中间点（不包括起始点）只包括 $1 \sim k$ 的最短距离。状态计算：可根据路径是否包含 $k$ 分两类，因此：

$$ f(k, i, j) = min(f(k - 1, i, j), f(k - 1, i, k) + f(k - 1, k, j)) $$

可以发现，当路径包含 $k$ 时，只需要以 $k$ 为中间点递推，不需要枚举其它点。

for (int k = 1; k <= n; k++)
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      f[i][j] = min(f[i][j], f[i][k] + f[k][j])

可以发现在实现时，第一维是可以去掉的，原因是 $f(i, k)$ 和 $f(k, j)$ 在本轮是不会被更新的，还保留着 $k - 1$ 层循环的值。之所以不会被更新，是因为运行到要更新它们的语句时，以其中之一举例：

f[i][k] = min(f[i][k], f[i][k] + f[k][k])

如果 $i, k$ 之间存在最短路，即连通且无负环，则 $f[k][k] = 0$，所以 $f[i][k]$ 不会被更新。