#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int NUMBER = 210, EDGE_NUMBER = NUMBER * 2;

int k, edge_number, start_node, end_node;
struct Edge {
    int ver1, ver2, val;
} arr[EDGE_NUMBER];
vector<int> nums;
int edge_index;

int get(int val) {
    return lower_bound(nums.begin(), nums.end(), val) - nums.begin();
}

int bellman_ford() {
    int dist[NUMBER];
    int temp[NUMBER];
    memset(dist, 0x3f, sizeof dist);
    dist[get(start_node)] = 0;

    for (int i = 1; i <= k; ++i) {
        memcpy(temp, dist, sizeof dist);
        memset(dist, 0x3f, sizeof dist);

        for (int j = 0; j < edge_index; ++j) {
            int ver1 = arr[j].ver1;
            int ver2 = arr[j].ver2;
            int val = arr[j].val;

            dist[ver2] = min(dist[ver2], temp[ver1] + val);
            dist[ver1] = min(dist[ver1], temp[ver2] + val);
        }
    }


    return dist[get(end_node)];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> k >> edge_number >> start_node >> end_node;
    while (edge_number--) {
        int ver1, ver2, val;
        cin >> val >> ver1 >> ver2;
        arr[edge_index++] = {ver1, ver2, val};
        nums.push_back(ver1), nums.push_back(ver2);
    }

    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

//  将节点编号进行离散化
    for (int i = 0; i < edge_index; ++i) {
        arr[i].ver1 = get(arr[i].ver1);
        arr[i].ver2 = get(arr[i].ver2);
    }

    cout << bellman_ford() << endl;

    return 0;
}