#include<bits/stdc++.h>
#define N 207
#define mod 10000
using namespace std;
struct matrix
{
    int A[N][N];
};
matrix g, ans;
int book[N*10];
matrix mul(matrix a, matrix b, int n)
{
    matrix r;
    memset(r.A, 0x3f, sizeof(r.A));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            for(int k = 1; k <= n; k++)
            {
                r.A[i][j] = min(r.A[i][j], a.A[i][k]+b.A[k][j]);
            }
        }
    }
    return r;
}
int main()
{
    int n, t, s, e, m = 0;
    freopen("relays.in","r",stdin);
	freopen("relays.out","w",stdout);
    scanf("%d%d%d%d", &n, &t, &s, &e);
    for(int i = 0; i <= 200; i++)
    {
        for(int j = 0; j <= 200; j++)
        {
            g.A[i][j] = 1e7;
            ans.A[i][j] = 1e7;
        }
    }
    for(int i = 1; i <= t; i++)
    {
        int x, y, l;
        scanf("%d%d%d", &l, &x, &y);
        if(book[x])
        {
            x = book[x];
        }
        else
        {
            book[x] = ++m;
            x = book[x];
        }
        if(book[y])
        {
            y = book[y];
        }
        else
        {
            book[y] = ++m;
            y = book[y];
        }
        g.A[x][y] = g.A[y][x] = l;
        ans.A[x][y] = ans.A[y][x] = l;
    }
    n--;
    while(n)
    {
        if(n&1)
        {
            ans = mul(g, ans, m);
        }
        g = mul(g, g, m);
        n >>= 1;
    }
    printf("%d\n", ans.A[book[s]][book[e]]);
    return 0;
}