'''
动态规划，dp(n, i, j)表示从i到j恰好经历n条边的最短距离，枚举中间点k
dp(n, i, j) = min{ dp(a, i, k) + dp(b, k, j) } 其中a+b = n

用倍增思想从底向上递推
要求dp(n, i, j), 把n用快速幂思想拆解成二进制的序列
如果n是2的整数次幂，走n条边的最短路长度，已经可以由走n//2条边的最短路长度推出来，
走n条边的最短路径就可以拆解成一系列2整数次幂边数的最短路连接而成
'''

from copy import deepcopy
max_step, m, s, e = map(int, input().split())


edges = {}
all_nodes = set()
for i in range(m):
    w, a, b = map(int, input().split())
    if (a, b) not in edges:
        edges[(a, b)] = w
    else:
        edges[(a, b)] = min(w, edges[(a, b)])

    if (b, a) not in edges:
        edges[(b, a)] = w
    else:
        edges[(b, a)] = min(w, edges[(b, a)])

    all_nodes.add(a)
    all_nodes.add(b)

idx2node = {i+1: node for i, node in enumerate(all_nodes)}
node2idx = {v: k for k, v in idx2node.items()}

n = len(all_nodes)      # 总节点数量

# 一开始g矩阵表示的是任意两个点走1条边的最短距离
g = [[0x7fffffff] * (n+1) for _ in range(n+1)]
tmp = [[0x7fffffff] * (n+1) for _ in range(n+1)]
for (a, b), w in edges.items():
    a, b = node2idx[a], node2idx[b]
    g[a][b] = w

ans = None


# 快速幂思想进行二进制拆分
while max_step > 0:
    if max_step & 1 != 0:
        if ans is None:
            ans = deepcopy(g)
        else:
            # ans增加g矩阵代表的步数
            for i in range(1, n+1):
                for j in range(1, n+1):
                    tmp[i][j] = 0x7fffffff

            for k in range(1, n+1):
                for i in range(1, n+1):
                    for j in range(1, n+1):
                        tmp[i][j] = min(tmp[i][j], ans[i][k] + g[k][j])

            ans, tmp = tmp, ans

    # g矩阵自己经历的边数更新成2倍
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            tmp[i][j] = 0x7fffffff

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                tmp[i][j] = min(tmp[i][j], g[i][k] + g[k][j])

    g, tmp = tmp, g

    max_step >>= 1

print(ans[node2idx[s]][node2idx[e]])