#include <iostream>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;

int K, T, S, E;

const int N = 210;
int res[N][N];
int g[N][N];
map<int, int> _m;
int t = 0;

void mul(int a[][N], int b[][N], int c[][N])
{
    static int temp[N][N];
    memset(temp, 0x3f, sizeof temp);
    for (int k = 1; k <= t; k ++)
        for (int i = 1; i <= t; i ++)
            for (int j = 1; j <= t; j ++)
                temp[i][j] = min(temp[i][j], b[i][k] + c[k][j]);
    memcpy(a, temp, sizeof temp);
}

void qmi()
{
    memset(res, 0x3f, sizeof res);

    for (int i = 1; i <= t; i ++) res[i][i] = 0;

    while(K)
    {
        if (K & 1) mul(res, res, g);
        mul(g, g, g);
        K >>= 1;
    }


}

int main(void)
{
    cin >> K >> T >> S >> E;
    memset(g, 0x3f, sizeof g);
    if (!_m.count(S)) _m[S] = ++ t;
    if (!_m.count(E)) _m[E] = ++ t;

    while (T --)
    {
        int a, b, c;
        cin >> c >> a >> b;
        if (!_m.count(a)) _m[a] = ++ t;
        if (!_m.count(b)) _m[b] = ++ t;
        g[_m[a]][_m[b]] = g[_m[b]][_m[a]] = min(c, g[_m[a]][_m[b]]);
    }

    qmi();
    cout << res[_m[S]][_m[E]] << endl;
    return 0;
}